Contains Duplicate

219. 存在重复元素II

分析

哈希表记录元素索引
- 用一个哈希表来记录每个元素上一次出现的索引。
遍历数组并检查条件
- 每次遍历到当前元素时，检查该元素是否已经存在于哈希表中：
  - 如果存在，比较当前索引和之前索引的差值是否小于等于 k，满足则返回 true
  - 如果不存在，或差值大于 k，则更新该元素的索引为当前索引
遍历结束仍未找到符合条件的元素，则返回 false

时间复杂度

时间复杂度 O(n)

空间复杂度

空间复杂度为 O(n)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution
{
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k)
    {
        std::unordered_map<int, int> hash;  // 用于存储元素及其最后一次出现的索引

        for (int i = 0; i < nums.size(); ++ i)
        {
            // 如果当前元素之前出现过，且索引之差小于等于 k
            if (hash.count(nums[i]) && i - hash[nums[i]] <= k)
                return true;  // 满足条件，直接返回 true

            hash[nums[i]] = i;  // 更新当前元素的索引
        }

        return false;  // 遍历结束未找到符合条件的元素，返回 false
    }
};