LeetCode_滑动窗口_简单_219.存在重复元素 II

╰半橙微兮° 2023-10-06 23:19 67阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 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

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/contains-duplicate-ii

## 2.思路 ##

（1）暴力穷举法  
该方法比较容易想到，即使用 2 层 for 循环来遍历数组 nums 中不同的 (nums\[i\], nums\[j\])，并判断 nums\[i\] == nums\[j\] 且 abs(i - j) <= k，如果存在满足条件的 (nums\[i\], nums\[j\])，则直接返回 true，否则返回 false。但是显然该方法的时间复杂度较高，为O(n2)，并且在 LeetCode 中提交时会出现“超出时间限制”的提示！

（2）滑动窗口  
思路参考[本题官方题解][Link 1]。

相似题目  
[LeetCode\_排序\_简单\_217.存在重复元素][LeetCode_217.]  
[LeetCode\_滑动窗口\_中等\_220.存在重复元素III][LeetCode_220._III]

## 3.代码实现（Java） ##

//思路1————暴力穷举法
    class Solution {
        
        public boolean containsNearbyDuplicate(int[] nums, int k) {
        
            int length = nums.length;
            for (int i = 0; i < length - 1; i++) {
        
                for (int j = i + 1; j < length; j++) {
        
                    if (nums[i] == nums[j] && Math.abs(i - j) <= k) {
        
                        return true;
                    }
                }
            }
            return false;
        }
    }

//思路2————滑动窗口
    class Solution {
        
    	public boolean containsNearbyDuplicate(int[] nums, int k) {
        
            int length = nums.length;
            Set<Integer> hashSet = new HashSet<>();
            for (int i = 0; i < length; i++) {
        
                //维护窗口大小
                if (i > k) {
        
                	//将窗口中最左端的元素移除
                    hashSet.remove(nums[i - k - 1]);
                }
                //add(e): 向集合中添加元素 e，如果此集合尚未包含指定的元素，则返回 true，否则返回 false
                if (!hashSet.add(nums[i])) {
        
                    return true;
                }
            }
            return false;
        }
    }

[Link 1]: https://leetcode.cn/problems/contains-duplicate-ii/solution/cun-zai-zhong-fu-yuan-su-ii-by-leetcode-kluvk/
[LeetCode_217.]: https://blog.csdn.net/weixin_43004044/article/details/119303009
[LeetCode_220._III]: https://blog.csdn.net/weixin_43004044/article/details/119317656