给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j] 并且 i 和 j 的差的绝对值最大为 k。
思路
- 双指针：时间复杂度O(kn)，k很大时退化为O(n^2)。
- 哈希表：时间复杂度O(n)。
代码(C++)
双指针
1
2
3
4
5
6
7
8
| if(nums.size()<2) return false;
for(auto p1=nums.cbegin();p1<nums.end();p1++)
for(auto p2=p1+1;p2<=p1+k && p2<nums.end();p2++)
{
if(*p2==*p1)
return true;
}
return false;
|
Map
1
2
3
4
5
6
7
8
9
10
11
| if(nums.size()<2) return false;
unordered_map<int,int> m;
for(int i=0;i<nums.size();i++)
{
if(m.find(nums[i])!=m.end())
return true
m[nums[i]]=i;
if(m.size()>k)
m.erase(nums[i-k]);
}
return false;
|
Set
1
2
3
4
5
6
7
8
9
10
11
| if(nums.size()<2) return false;
unordered_set<int> s;
for(int i=0;i<nums.size();i++)
{
if(s.find(nums[i])!=s.end())
return true
s.insert(nums[i]);
if(s.size()>k)
s.erase(nums[i-k]);
}
return false;
|