219.存在重复元素 II

题目:219.存在重复元素 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 <= 10^5
-10^9 <= nums[i] <= 10^9
0 <= k <= 10^5

思路1

1. 创建一个哈希表，用于记录每个元素的最新索引。
2. 遍历数组，对于每个元素：
   • 如果该元素已经在哈希表中存在，并且当前索引与记录的索引之间的距离小于等于 k，则返回 true。
   • 更新该元素在哈希表中的最新索引。
3. 如果遍历完数组没有找到满足条件的元素，返回 false。

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

代码

public boolean containsNearbyDuplicate(int[] nums, int k) {
    Map<Integer, Integer> numIndex = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        // 检查哈希表中是否存在相同元素，并且索引距离小于等于 k
        if (numIndex.containsKey(nums[i]) && i - numIndex.get(nums[i]) <= k) {
            return true;
        }
        numIndex.put(nums[i], i);
    }
    return false;
}

思路2

1. 使用一个哈希表来存储当前窗口内的元素及其索引。
2. 使用一个固定大小为 k 的滑动窗口来遍历数组。
3. 在遍历过程中，将当前元素加入滑动窗口，如果滑动窗口的大小超过 k，则移除滑动窗口最左侧的元素。
4. 检查当前元素是否已经在滑动窗口中存在，如果存在则返回 true，否则继续。

• 时间复杂度:O()
• 空间复杂度:O()

代码

public boolean containsNearbyDuplicate(int[] nums, int k) {
    // 创建一个哈希表来记录当前窗口内的元素及其索引
    Map<Integer, Integer> numIndex = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        // 检查当前元素是否已经在滑动窗口内
        if (numIndex.containsKey(nums[i])) {
            return true;
        }
        numIndex.put(nums[i], i);
        // 如果滑动窗口的大小超过 k，则移除最左侧的元素
        if (numIndex.size() > k) {
            numIndex.remove(nums[i - k]);
        }
    }
    return false;
}