目录

1，题目描述

英文描述

中文描述

2，解题思路

3，AC代码

C++

Java

4，解题过程

第一博

第二搏

---

1，题目描述

原题链接219. 存在重复元素 II

英文描述

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.

Example 1:

Input: nums = [1,2,3,1], k = 3 Output: true Example 2:

Input: nums = [1,0,1,1], k = 1 Output: true Example 3:

Input: nums = [1,2,3,1,2,3], k = 2 Output: false

中文描述

给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的 绝对值 至多为 k。

 

示例 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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/contains-duplicate-ii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 

2，解题思路

参考@力扣 (LeetCode)【存在重复元素 II】

采用set+滑动窗口的方法；

以set集合为基础，设置滑动窗口大小为k；

遍历数组元素，若元素存在于set中，说明k范围内存在符合条件的数据，返回true；

若不存在，则将其插入到set集合中。当集合大小已达到k，则先删除最旧的元素record.erase(nums[i - k]);，再插入当前元素；

 

3，AC代码

C++

class Solution { public: bool containsNearbyDuplicate(vector<int>& nums, int k) { if(nums.size() == 0 || k == 0) return false; unordered_set<int> record; for(int i = 0; i < nums.size(); i++) { if(record.count(nums[i]) != 0) return true; if(record.size() == k) { // 窗口k已满 需要删除最旧的元素 record.erase(nums[i - k]); } record.insert(nums[i]); } return false; } };

Java

class Solution { public boolean containsNearbyDuplicate(int[] nums, int k) { if(nums.length == 0 || k == 0) return false; Set<Integer> recode = new HashSet<>(); for(int i = 0; i < nums.length; i++) { if(recode.contains(nums[i])) return true; if(recode.size() == k) recode.remove(nums[i - k]); recode.add(nums[i]); } return false; } }

4，解题过程

第一博

使用record（map类型），key存放nums[i]，value存放该值对应的索引；

若当前遍历元素nums[i]在record中存在相同的key时，检查当前索引 i 与key对应的value之差，满足条件返回true，否则更新record中key对应的value为 i ；

class Solution { public: bool containsNearbyDuplicate(vector<int>& nums, int k) { if(nums.size() == 0) return false; unordered_map<int, int> record; for(int i = 0; i < nums.size(); i++) { if(record.find(nums[i]) == record.end()) { record[nums[i]] = i; }else { if(i - record[nums[i]] <= k) return true; else record[nums[i]] = i; } } return false; } };

第二搏

官方解法使用set + 滑动窗口，更巧妙！

set维护大小为k的窗口，当前元素存在于窗口内则返回true，否则插入set中；

若set已满则删除最旧的元素record.erase(nums[i - k])（i 为当前遍历到的索引）；