LeetCode 第219题：存在重复元素 II

题目描述

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

难度

简单

题目链接

点击在LeetCode中查看题目

示例

示例 1：

输入：nums = [1,2,3,1], k = 3
输出：true

示例 2：

输入：nums = [1,0,1,1], k = 1
输出：true

示例 3：

输入：nums = [1,2,3,1,2,3], k = 2
输出：false

提示

1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
0 <= k <= 10^5

解题思路

这个问题要求判断数组中是否存在两个相同的元素，且它们的位置索引差不超过k。解决这个问题有以下几种方法：

方法一：滑动窗口 + 哈希表

使用一个大小最多为k的滑动窗口来检查数组中的元素。采用哈希表（HashSet）来高效地存储窗口中的元素。

具体步骤：

初始化一个哈希集合，用于存储窗口内的元素
遍历数组： a. 如果当前元素在哈希集合中已存在，返回true b. 将当前元素加入哈希集合 c. 如果窗口大小超过k，则移除最早加入窗口的元素
如果遍历完数组还没有找到满足条件的元素，返回false

时间复杂度：O(n)，其中n是数组长度空间复杂度：O(min(n, k))，哈希集合最多存储k个元素

方法二：哈希表记录索引

使用哈希表记录每个元素最后一次出现的索引位置。

具体步骤：

初始化一个哈希表，用于存储元素及其索引
遍历数组： a. 如果当前元素已在哈希表中，且当前索引与上次索引的差不超过k，返回true b. 将当前元素及其索引更新到哈希表中
如果遍历完数组还没有找到满足条件的元素，返回false

时间复杂度：O(n)，其中n是数组长度空间复杂度：O(n)，最坏情况下所有元素都不同，哈希表需存储n个元素

代码实现

C# 实现

using System;
using System.Collections.Generic;

public class Solution {
    // 方法一：滑动窗口 + 哈希集合
    public bool ContainsNearbyDuplicate(int[] nums, int k) {
        HashSet<int> set = new HashSet<int>();
        for (int i = 0; i < nums.Length; i++) {
            // 如果集合中已存在当前元素，返回true
            if (set.Contains(nums[i])) {
                return true;
            }
            
            // 将当前元素加入集合
            set.Add(nums[i]);
            
            // 如果集合大小超过k，移除最早加入的元素
            if (set.Count > k) {
                set.Remove(nums[i - k]);
            }
        }
        return false;
    }
    
    // 方法二：哈希表记录索引
    public bool ContainsNearbyDuplicate2(int[] nums, int k) {
        Dictionary<int, int> map = new Dictionary<int, int>();
        for (int i = 0; i < nums.Length; i++) {
            // 如果当前元素已在哈希表中，检查索引差
            if (map.ContainsKey(nums[i]) && i - map[nums[i]] <= k) {
                return true;
            }
            
            // 更新元素的最新索引
            map[nums[i]] = i;
        }
        return false;
    }
}

Python 实现

class Solution:
    # 方法一：滑动窗口 + 哈希集合
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        window = set()
        for i, num in enumerate(nums):
            # 如果当前元素在窗口中，返回true
            if num in window:
                return True
            
            # 将当前元素加入窗口
            window.add(num)
            
            # 如果窗口大小超过k，移除最早加入的元素
            if len(window) > k:
                window.remove(nums[i - k])
        
        return False
    
    # 方法二：哈希表记录索引
    def containsNearbyDuplicate2(self, nums: List[int], k: int) -> bool:
        index_map = {}
        for i, num in enumerate(nums):
            # 如果当前元素已在哈希表中，检查索引差
            if num in index_map and i - index_map[num] <= k:
                return True
            
            # 更新元素的最新索引
            index_map[num] = i
        
        return False

C++ 实现

#include <vector>
#include <unordered_set>
#include <unordered_map>
using namespace std;

class Solution {
public:
    // 方法一：滑动窗口 + 哈希集合
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_set<int> window;
        for (int i = 0; i < nums.size(); i++) {
            // 如果当前元素在窗口中，返回true
            if (window.count(nums[i])) {
                return true;
            }
            
            // 将当前元素加入窗口
            window.insert(nums[i]);
            
            // 如果窗口大小超过k，移除最早加入的元素
            if (window.size() > k) {
                window.erase(nums[i - k]);
            }
        }
        return false;
    }
    
    // 方法二：哈希表记录索引
    bool containsNearbyDuplicate2(vector<int>& nums, int k) {
        unordered_map<int, int> index_map;
        for (int i = 0; i < nums.size(); i++) {
            // 如果当前元素已在哈希表中，检查索引差
            if (index_map.count(nums[i]) && i - index_map[nums[i]] <= k) {
                return true;
            }
            
            // 更新元素的最新索引
            index_map[nums[i]] = i;
        }
        return false;
    }
};

性能分析

各语言实现的性能对比：

实现语言	方法	执行用时	内存消耗	说明
C#	滑动窗口 + 哈希集合	204 ms	53.4 MB	时间复杂度 O(n)，空间复杂度 O(min(n, k))
C#	哈希表记录索引	180 ms	54.7 MB	时间复杂度 O(n)，空间复杂度 O(n)
Python	滑动窗口 + 哈希集合	84 ms	27.2 MB	时间复杂度 O(n)，空间复杂度 O(min(n, k))
Python	哈希表记录索引	76 ms	27.8 MB	时间复杂度 O(n)，空间复杂度 O(n)
C++	滑动窗口 + 哈希集合	96 ms	77.2 MB	时间复杂度 O(n)，空间复杂度 O(min(n, k))
C++	哈希表记录索引	88 ms	80.9 MB	时间复杂度 O(n)，空间复杂度 O(n)

补充说明

代码亮点

滑动窗口方法巧妙地维护了一个最大长度为k的窗口，确保在O(1)时间内检查重复元素
哈希表记录索引的方法避免了不必要的元素删除操作，能更快地检查相同元素的索引距离
两种方法都充分利用了哈希表的O(1)查找特性

优化方向

当数组长度远大于k时，滑动窗口+哈希集合方法更为空间高效
如果数组中存在大量相同的元素，哈希表记录索引的方法更为时间高效
在极端情况下(k非常大)，可以考虑先检查数组是否有重复元素，若无则直接返回false

解题难点

理解题目要求中“索引差不超过k”的含义
滑动窗口大小的控制和维护
选择合适的数据结构来高效地查找重复元素

常见错误

混淆了索引差的计算方式，错误地使用 j - i <= k 而不是 abs(i - j) <= k
没有正确维护滑动窗口的大小，导致窗口超过k个元素
在方法二中，没有更新元素的最新索引，而是保留了第一次出现的索引
忘记处理数组中存在相同元素但索引差大于k的情况