Leetcode - 重复元素III

问题

给定一个整数数组，判断数组中是否有两个不同的索引 i 和 j，使得 nums [i] 和 nums [j] 的差的绝对值最大为 t，并且 i 和 j 之间的差的绝对值最大为 ķ。

思路

1. 双指针：略过。
2. Set：维护一个大小为k的set，由于set自动排序的特性，可以找出不小于nums[i]-t的值，然后判断该值是否同时不大于nums[i]+t。
3. 哈希+桶:将nums元素分散到大小为t+1的桶中，然后以桶id作为键，nums[i]作为值存入hash表，只需要查找nums[i]所在的桶和相邻的两个桶即可。

代码(C++)

Set

if(k<1 || nums.size()<2 || t<0) return false;
set<int> s;
for(int i=0;i<nums.size();i++)
{
	auto ps=s.lower_bound(nums[i]-t);	//不小于nums[i]-t
	if(ps!=s.end() && abs((*ps)-nums[i])<=t)	//不大于nums[i]+t
		return true;
	s.insert(nums[i]);
	if(s.size()>k)
		s.erase(nums[i-k]);
}
return false;

哈希+桶

int getid(int n,int s)	//计算桶id，除法保证同一桶元素相差[0~s-1]
{
	return n<0?(n+1)/s-1:n/s;	//eg:[-s+1,-1]/s=0，如果不特殊处理则与[0,s-1]桶id混淆
}

if(k<1 || nums.size()<2 || t<0) return false;
unordered_map<int,int> m;
int sb=t+1;	//桶大小，0~t
int id;
int n;
for(int i=0;i<nums.size();i++)
{
	n=nums[i];
	id=getid(n,sb);
	if(m.count(id))	//同一桶必然满足条件
		return true;
	if(m.count(id-1) && n-m[id-1]<=t)	//左
		return true;
	if(m.count(id+1) && m[id+1]-n<=t)	//右
		return true;
	m[id]=n;
	if(m.size()>k)
		m.erase(m.find(getid(nums[i-k],sb)));
}
return false;