題目來源
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.
第一想法就是把每種情況都列一下获三，復雜度O(kn)。
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
int n = nums.size();
for (int i=0; i<n-1; i++)
for (int j=i+1; j<=i+k && j<n; j++)
if (nums[i] == nums[j])
return true;
return false;
}
};
不出意外TLE了。
然后又想了想舔哪，用哈希惭缰，記錄下每個數(shù)字出現(xiàn)的位置箱叁。
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
unordered_map<int, vector<int>> map;
int n = nums.size();
for (int i=0; i<n; i++) {
if (map.find(nums[i])!=map.end() && (i - map[nums[i]].back() <= k))
return true;
map[nums[i]].push_back(i);
}
return false;
}
};
看了看答案驼卖，發(fā)現(xiàn)只要記錄k個就可以了筏餐，里面有重復的就true。
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
unordered_set<int> s;
int n = nums.size();
for (int i=0; i<n; i++) {
if (i > k)
s.erase(nums[i-k-1]);
if (s.find(nums[i]) != s.end())
return true;
s.insert(nums[i]);
}
return false;
}
};
