邢台企业做网站推广,台州网站建设方案优化,青海h5页面制作,公司网站设计广州219. 存在重复元素 II 这道题可以用两个方法解决。
哈希表
从左到右遍历数组#xff0c;并将数组的下标存到hash中#xff0c;在遍历数字的过程中#xff0c;如果hash中不存在nums[i]#xff0c;将nums[i]加入到hash当中#xff0c;若存在#xff0c;则判断下标之间的关…219. 存在重复元素 II 这道题可以用两个方法解决。
哈希表
从左到右遍历数组并将数组的下标存到hash中在遍历数字的过程中如果hash中不存在nums[i]将nums[i]加入到hash当中若存在则判断下标之间的关系即可。
class Solution {
public:bool containsNearbyDuplicate(vectorint nums, int k) {unordered_mapint, 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;}
};
滑动窗口
要满足ABS(I - J) K可以想象一个窗口窗口中的数字必然满足条件。当nums中的每个长度不超过k 1的滑动窗口同一个滑动窗口中的任意两个下标差绝对不会超过k。
class Solution {
public:bool containsNearbyDuplicate(vectorint nums, int k) {unordered_setint 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;}
};
