Contains Duplicate 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.
题目大意:
给定一个数组nums和一个数字k。判断是否存在nums[i] == nums[j] 并且j - i <= k。
我们可以利用set去除重复元素的特性，因为set会自动排序会影响结果判断，因此我们用unordered_set。
我们让unordered_set中最多存储k个数字，不够k个就插入，如果超过k个就将最前面的元素“擦除”，在每次插入的时候判断将要插入的元素在定义的unordered_set中是否已经存在，如果已经存在那么返回true。
题目代码:
class Solution {
public:bool containsNearbyDuplicate(vector<int>& nums, int k) {int n = nums.size();unordered_set<int>us;int start = 0, end = 0;for(int i = 0; i < n; i++){if(us.count(nums[i]) == 0){us.insert(nums[i]);end++;}else{return true;}if(end - start > k){us.erase(nums[start]);start++;}}return false;}
};