219.存在重复元素 II

1、题干

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

 

示例 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 <= 105
• -109 <= nums[i] <= 109
• 0 <= k <= 105

2、解法1-哈希映射

遍历数组所有元素，并将当前数字和索引作为键值存入哈希映射 map 中，如果当前数字 nums[i] 已存在于 map 中且其索引与当前索引的差值不大于 k 则返回 true，遍历结束仍未找到符合条件的数字则返回 false

3、复杂度

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

4、代码

var containsNearbyDuplicate = function (nums, k) {
    const map = new Map();
    for (let i = 0; i < nums.length; i++) {
        if (map.has(nums[i]) && i - map.get(nums[i]) <= k) return true;
        map.set(nums[i], i);
    }
    return false;
};

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        map = {}
        for i in range(len(nums)):
            if(nums[i] in map and i - map[nums[i]] <= k):
                return True
            map[nums[i]] = i
        return False

5、解法2-滑动窗口+哈希集合

遍历数组所有元素，使用哈希集合 set 作为滑动窗口容器存储数组中连续的 k 个元素，索引 i 大于 k 之后需要剔除滑动窗口容器的首个元素 nums[i - k - 1] 以保证其长度不超过 k，如果当前元素已存在于哈希集合则说明二者索引差值不大于 k 应返回 true，遍历结束仍未找到符合条件的数字则返回 false

解法1的优势在于更容易想到和理解。解法2的优势在于只需要存储值而不需要存储键值对，因此空间占用会更少；另外当 k 比 nums.length 小的情况下，解法2的空间复杂度会更小且不受 nums.length 变大而影响。

6、复杂度

• 时间复杂度：$O(n)$
• 空间复杂度：$O(k)$

7、代码

var containsNearbyDuplicate = function (nums, k) {
    const set = new Set();
    for (let i = 0; i < nums.length; i++) {
        if (i > k) set.delete(nums[i - k - 1]);
        if (set.has(nums[i])) return true;
        set.add(nums[i]);
    }
    return false;
};

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        s = set()
        for i in range(len(nums)):
            if(i > k):
                s.remove(nums[i - k - 1])
            if(nums[i] in s):
                return True
            s.add(nums[i])
        return False