LeetCode - 存在重复元素

219. 存在重复元素 II

这道题可以用两个方法解决。

1. 哈希表

从左到右遍历数组，并将数组的下标存到hash中，在遍历数字的过程中，如果hash中不存在nums[i]，将nums[i]加入到hash当中，若存在，则判断下标之间的关系即可。

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

1. 滑动窗口

要满足ABS(I - J) <= K，可以想象一个窗口，窗口中的数字必然满足条件。当nums中的每个长度不超过k + 1的滑动窗口，同一个滑动窗口中的任意两个下标差绝对不会超过k。

class Solution {
public:bool containsNearbyDuplicate(vector<int>& nums, int k) {unordered_set<int> s;int length = nums.size();for (int i = 0; i < length; i++) {if (i > k) {s.erase(nums[i - k - 1]);}if (s.count(nums[i])) {return true;}s.emplace(nums[i]);}return false;}
};