1. Description of the topic

There is a duplicate element II

English description

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

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

Output: false

Product description

Given an array of integers and an integer k, determine whether there are two different indexes I and j in the array such that nums [I] = nums [j] and the absolute value of the 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

Source: LeetCode link: leetcode-cn.com/problems/co… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

2

See @LeetCode [duplicate element II]

The method of set+ sliding window is adopted.

Based on set set, set the sliding window size to K;

Iterate over a number of elements, if the element exists in set, it means that there is data in the range of K that meets the conditions, and return true;

If not, it is inserted into the set collection. Erase (nums[i-k]); erase(nums[i-k]); , and then insert the current element;

3. AC code

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) {record. Erase (nums[i-k]); } record.insert(nums[i]); } return false; }};Copy the code

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; }}Copy the code

4. The process of solving the problem

The first,

Record (map type), key stores NUMS [I], value stores the index corresponding to the value.

If the current traversal element NUMS [I] in the record there is the same key, check the current index I and key corresponding value difference, meet the conditions return true, otherwise update the record key corresponding value is 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; }};Copy the code

​

The second stroke

The official solution uses set + sliding window, more ingenious!

Set maintains a window of size K, returns true if the current element exists in the window, otherwise inserts into the set;

Erase (nums[i-k]) (I is the current iterated index);

​

​