46.存在重复元素 II

题目

给你一个整数数组 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

思路

方法一: 哈希表

用哈希表保存出现过的数字以及索引，下一次如果哈希表中存在这个数字了就判断索引相减是不是小于等于k

class Solution {
    fun containsNearbyDuplicate(nums: IntArray, k: Int): Boolean {
        val map = HashMap<Int, Int>()
        for (i in nums.indices) {
            if (map.contains(nums[i]) && i - map[nums[i]]!! <= k) {
                return true
            }
            map[nums[i]] = i
        }
        return false
    }
}

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        map = defaultdict()
        for i, num in enumerate(nums):
            if num in map:
                m = map[num]
                if i - m > k:
                    return True
            map[num] = i
        return False

复杂度分析:

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

方法二: 定长滑动窗口

整理题意：是否存在长度不超过的 k+1 窗口，窗口内有相同元素。

所以可以用滑动窗口 + HashSet的方式，

在窗口内始终维护最近k个元素，新元素进来前检查set中是否已经存在，同时在set中元素个数超过k时移除最前面的元素，保持set中使用有k个元素，这样就能够将空间 复杂度从O(n)降到O(k)

class Solution {
    fun containsNearbyDuplicate(nums: IntArray, k: Int): Boolean {
        val set = HashSet<Int>()
        for (i in nums.indices) {
            if (!set.add(nums[i])) {
                // 已存在，且窗口内
                return true
            }
            if (set.size > k) {
                // 移除窗口最左元素
                set.remove(nums[i - k])
            }
        }
        return false
    }
}

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

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        int n = nums.length;
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < n; i++) {
            if (i > k) set.remove(nums[i - k - 1]);
            if (set.contains(nums[i])) return true;
            set.add(nums[i]);
        }
        return false;
    }
}

复杂度分析:

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

• 下一题

• 邮箱 ：charon.chui@gmail.com
• Good Luck!