网站后期维护收费,网站设计的主要内容,厦门网站开发网站建设网站,哈尔滨网站建设 博客题目 给你一个整数数组 nums 和一个整数 k #xff0c;判断数组中是否存在两个 不同的索引 i 和 j #xff0c;满足 nums[i] nums[j] 且 abs(i - j) k 。如果存在#xff0c;返回 true #xff1b;否则#xff0c;返回 false 。 示例 1#xff1a; 输入#xff1a…题目 给你一个整数数组 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 思路一
暴力解法使用两层for循环遍历所有元素判断num[i]num[j] Math.abs(i-j)k。时间复杂度为On²能解题目但是力扣无法通过会超时。
代码
class Solution {public boolean containsNearbyDuplicate(int[] nums, int k) {for (int i 0; i nums.length - 1; i) {for (int j i 1; j nums.length; j) {if (nums[i] nums[j] Math.abs(i - j) k) {return true;}}}return false;}
}思路二
滑动窗口使用leftright两个指针维护一个大小为k的窗口使用set来判断窗口内是否有相同的元素。
代码
class Solution {public boolean containsNearbyDuplicate(int[] nums, int k) {//用来判断是否有相同元素SetInteger set new HashSet();int left 0;for (int right 0; right nums.length; right) {//如果窗口大小大于k了则左指针前移缩小窗口大小if (Math.abs(left - right) k) {set.remove(nums[left]);left;}//如果当前的窗口内有相同的元素则返回trueif (set.contains(nums[right])) {return true;} else {//没有相同的元素就添加到set中set.add(nums[right]);}}return false;}
}
