做网站租服务器一年多少钱,工作台,4.9.8wordpress,最新新闻热点事件摘抄及评论力扣#xff1a;219. 存在重复元素 II
给你一个整数数组 nums 和一个整数 k #xff0c;判断数组中是否存在两个 不同的索引 i 和 j #xff0c;满足 nums[i] nums[j] 且 abs(i - j) k 。如果存在#xff0c;返回 true #xff1b;否则#xff0c;返回 false 。 …力扣219. 存在重复元素 II
给你一个整数数组 nums 和一个整数 k 判断数组中是否存在两个 不同的索引 i 和 j 满足 nums[i] nums[j] 且 abs(i - j) k 。如果存在返回 true 否则返回 false 。
方法一哈希表
#includeiostream
#includeunordered_mapusing namespace std;class Solution {
public:bool containsNearbyDuplicate(vectorint nums, int k) {unordered_mapint, int m;for (int i 0; i nums.size(); i) {if (m.count(nums[i]) 0 abs(m[nums[i]] - i) k) {return true;}m[nums[i]] i;}return false;}
};int main()
{ Solution solution;vectorint duplicate{ 1,2,3,1 };int result solution.containsNearbyDuplicate(duplicate,3);cout result endl;return 0;
}方法二滑动窗口
制造一个i-k-1的窗口加入当前窗口位置的数组成员超过窗口范围的删除在此窗口中查找有无重复的数字有则为真无则为假
#includeiostream
#includeunordered_setusing namespace std;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;}
};int main()
{Solution solution;vectorint duplicate{ 1,2,3,1 };int result solution.containsNearbyDuplicate(duplicate, 3);cout result endl;return 0;
}
