存在重复元素 II[简单]

优质博文：IT-BLOG-CN
在这里插入图片描述

一、题目

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

二、代码

【1】滑动窗口： 数组nums中的每个长度不超过k + 1的滑动窗口，同一个滑动窗口中的任意两个下标差的绝对值不超过k。如果存在一个滑动窗口，其中有重复元素，则存在两个不同的下标i和j满足nums[i] = nums[j]且∣i−j∣ ≤ k。如果所有滑动窗口中都没有重复元素，则不存在符合要求的下标。因此，只要遍历每个滑动窗口，判断滑动窗口中是否有重复元素即可。

如果一个滑动窗口的结束下标是i，则该滑动窗口的开始下标是max⁡(0,i−k)。可以使用哈希集合存储滑动窗口中的元素。从左到右遍历数组nums，当遍历到下标i时，具体操作如下：
1、如果i > k，则下标i − k − 1处的元素被移出滑动窗口，因此将nums[i−k−1]从哈希集合中删除；
2、判断nums[i]是否在哈希集合中，如果在哈希集合中则在同一个滑动窗口中有重复元素，返回true，如果不在哈希集合中则将其加入哈希集合。
当遍历结束时，如果所有滑动窗口中都没有重复元素，返回false。

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        // 思想，采用滑动窗口的思想，定义两个指针，之间的最大距离为k，如果超过k，则进行下一次判断，慢指针向前一步；
        if (nums != null && nums.length == 0) {
            return false;
        }

        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; (j <= i + k && j < nums.length); j++) {
                if (nums[i] == nums[j]) {
                    return true;
                }
            }
        }
        return false;
    }
}

时间复杂度： O(n)其中n是数组nums的长度。需要遍历数组一次，对于每个元素，哈希集合的操作时间都是O(1)。
空间复杂度： O(k)其中k是判断重复元素时允许的下标差的绝对值的最大值。需要使用哈希集合存储滑动窗口中的元素，任意时刻滑动窗口中的元素个数最多为k+1个。

【2】哈希表： 从左到右遍历数组nums，当遍历到下标i时，如果存在下标j<i使得nums[i]=nums[j]，则当i−j≤k时即找到了两个符合要求的下标j和i。如果在下标i之前存在多个元素都和nums[i]相等，为了判断是否存在满足nums[i]=nums[j]且i−j≤k的下标j，应该在这些元素中寻找下标最大的元素，将最大下标记为j，判断i−j≤k是否成立。

如果i−j≤k，则找到了两个符合要求的下标j和i；如果i−j>k，则在下标i之前不存在任何元素满足与nums[i]相等且下标差的绝对值不超过k，当遍历到下标i时，如果在下标i之前存在与nums[i]相等的元素，应该在这些元素中寻找最大的下标j，判断i−j≤k是否成立。

可以使用哈希表记录每个元素的最大下标。从左到右遍历数组nums，当遍历到下标i时，进行如下操作：
1、如果哈希表中已经存在和nums[i]相等的元素且该元素在哈希表中记录的下标j满足i−j≤k，返回true；
2、将nums[i]和下标i存入哈希表，此时i是nums[i]的最大下标。
上述两步操作的顺序不能改变，因为当遍历到下标i时，只能在下标i之前的元素中寻找与当前元素相等的元素及该元素的最大下标。当遍历结束时，如果没有遇到两个相等元素的下标差的绝对值不超过k，返回false。

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        // 思想：通过hashmap[key=nums中的元素，value = 下表]，每次判断元素是否存在，存在则获取下表与当前的元素进行比较；
        if (nums != null && nums.length == 0) {
            return false;
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i]) && i - map.get(nums[i]) <= k) {
                return true;
            }
            map.put(nums[i], i);
        } 
        return false;
    }
}