赞
踩
给你一个整数数组 nums 和一个整数 k ,判断数组中是否存在两个 不同的索引 i 和 j ,满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在,返回 true ;否则,返回 false 。
#include<iostream> #include<unordered_map> using namespace std; class Solution { public: bool containsNearbyDuplicate(vector<int>& nums, int k) { unordered_map<int, 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; vector<int> duplicate{ 1,2,3,1 }; int result = solution.containsNearbyDuplicate(duplicate,3); cout << result << endl; return 0; }
制造一个i-k-1的窗口,加入当前窗口位置的数组成员,超过窗口范围的删除,在此窗口中查找有无重复的数字,有则为真,无则为假
#include<iostream> #include<unordered_set> using namespace std; 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; } }; int main() { Solution solution; vector<int> duplicate{ 1,2,3,1 }; int result = solution.containsNearbyDuplicate(duplicate, 3); cout << result << endl; return 0; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。