LeetCode 解题：使用滑动窗口和哈希映射解决「存在重复元素 II」

"该资源为一个关于LeetCode问题“contains-duplicate-ii”的解题手稿，版本号为V1.111，主要涉及数据结构、C++编程语言以及LeetCode平台。手稿中提供了两种解题方法，分别是滑动窗口法和使用map数据结构保存法。" 在LeetCode的这个问题“contains-duplicate-ii”中，目标是判断给定的整数数组`nums`中是否存在两个不同的索引`i`和`j`，使得`nums[i] = nums[j]`且`|i - j| <= k`。这个问题涉及到数组处理和高效查找算法。 ### 方法一：滑动窗口法 滑动窗口法的基本思想是维护一个大小为`k+1`的窗口，遍历数组，每次移动窗口的左边界，检查窗口内是否有重复元素。此方法的时间复杂度为`O(n)`，因为需要遍历整个数组，空间复杂度为`O(1)`，只使用了常量级别的额外空间。然而，实际运行时可能会因为窗口的不断调整导致超时。 ```cpp // 示例代码 for (int i = 0; i <= n - k; ++i) { for (int j = i + 1; j <= i + k; ++j) { if (nums[i] == nums[j]) { return true; } } } ``` ### 方法二：map数据结构保存法 使用map存储数组元素及其对应的最新索引，遍历数组时，检查当前元素是否已经在map中出现过。这种方法的时间复杂度为`O(n log n)`，其中`log n`是map插入和查找操作的时间复杂度，空间复杂度为`O(n)`，因为map可能需要存储数组中的所有元素。 ```cpp unordered_map<int, int> m; for (int i = 0; i < len; ++i) { if (m.find(nums[i]) != m.end() && i - m[nums[i]] <= k) { return true; } m[nums[i]] = i; } return false; ``` ### 方法二（优化）： 优化后的map法不再保存每个元素的所有出现位置，而是仅记录最近出现的位置。这样可以减少空间使用，同时保持相同的时间复杂度。 ```cpp unordered_map<int, int> m; for (int i = 0; i < len; ++i) { if (m.find(nums[i]) != m.end() && i - m[nums[i]] <= k) { return true; } // 更新或插入元素 m[nums[i]] = i; } return false; ``` 注意，计算map的时间复杂度时，通常考虑的是每个元素的插入和查找操作。对于有序容器如`std::map`，插入和查找的时间复杂度为`O(log n)`；对于无序容器如`std::unordered_map`，平均情况下插入和查找的时间复杂度为`O(1)`，但在最坏情况下可能达到`O(n)`。空间复杂度取决于map中存储的键值对数量，即数组中不同元素的数量，因此为`O(n)`。 总结，解决此类问题的关键在于有效地查找重复元素，滑动窗口法虽然简单但可能效率不够，而map法通过牺牲部分空间换取更快的查找速度。优化后的map法在空间上进一步优化，适用于内存有限的情况。