Easy

题目描述

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

示例 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。如果满足条件则返回 true，否则更新该元素的最新索引。

方法二：滑动窗口 + 哈希集合 维护一个大小为 k+1 的滑动窗口，用哈希集合存储窗口内的元素。如果当前元素已在集合中，说明找到了距离不超过 k 的重复元素。当窗口大小超过 k+1 时，移除最左边的元素。

推荐方法一，因为它的实现更直观，空间复杂度在最坏情况下也不会超过 O(n)，而方法二需要额外的窗口维护逻辑。

两种方法的时间复杂度都是 O(n)，但方法一的常数因子更小。

代码实现

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, int> indexMap;
        
        for (int i = 0; i < nums.size(); i++) {
            if (indexMap.find(nums[i]) != indexMap.end() && i - indexMap[nums[i]] <= k) {
                return true;
            }
            indexMap[nums[i]] = i;
        }
        
        return false;
    }
};

class Solution:
    def containsNearbyDuplicate(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

public class Solution {
    public bool ContainsNearbyDuplicate(int[] nums, int k) {
        Dictionary<int, int> indexMap = new Dictionary<int, int>();
        
        for (int i = 0; i < nums.Length; i++) {
            if (indexMap.ContainsKey(nums[i]) && i - indexMap[nums[i]] <= k) {
                return true;
            }
            indexMap[nums[i]] = i;
        }
        
        return false;
    }
}

var containsNearbyDuplicate = function(nums, k) {
    const indexMap = new Map();
    
    for (let i = 0; i < nums.length; i++) {
        if (indexMap.has(nums[i]) && i - indexMap.get(nums[i]) <= k) {
            return true;
        }
        indexMap.set(nums[i], i);
    }
    
    return false;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型哈希表方法滑动窗口方法
时间复杂度O(n)O(n)
空间复杂度O(min(n, k))O(min(n, k))

其中 n 是数组长度。空间复杂度取决于哈希表/集合中存储的元素个数，最多为 min(n, k+1)。

相关题目