【力扣】219. 存在重复元素 II

标题

   给你一个整数数组 nums 和一个整数 k ，判定数组中是否存在两个 差别的索引 i 和 j ，满意 nums == 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 <= 109
0 <= k <= 105
  思绪一

暴力解法，利用两层for循环遍历全部元素，判定num==num[j] && Math.abs(i-j)<=k。时间复杂度为On²，能解标题，但是力扣无法通过，会超时。
代码

1. class Solution {
2.     public boolean containsNearbyDuplicate(int[] nums, int k) {
3.         for (int i = 0; i < nums.length - 1; i++) {
4.             for (int j = i + 1; j < nums.length; j++) {
5.                 if (nums[i] == nums[j] && Math.abs(i - j) <= k) {
6.                     return true;
7.                 }
8.             }
9.         }
10.         return false;
11.     }
12. }

复制代码

思绪二

滑动窗口，利用left，right两个指针维护一个巨细为k的窗口，利用set来判定窗口内是否有相同的元素。
代码

1. class Solution {
2.     public boolean containsNearbyDuplicate(int[] nums, int k) {
3.     //用来判断是否有相同元素
4.         Set<Integer> set = new HashSet<>();
5.         int left = 0;
6.         for (int right = 0; right < nums.length; right++) {
7.         //如果窗口大小大于k了，则左指针前移，缩小窗口大小，
8.             if (Math.abs(left - right) > k) {
9.                 set.remove(nums[left]);
10.                 left++;
11.             }
12.             //如果当前的窗口内有相同的元素，则返回true
13.             if (set.contains(nums[right])) {
14.                 return true;
15.             } else {
16.             //没有相同的元素就添加到set中
17.                 set.add(nums[right]);
18.             }
19.         }
20.         return false;
21.     }
22. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。