LeetCode Contains Duplicate III

LeetCode Contains Duplicate III

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.


给定一个数组,问是否存在两个相距k之内的差的绝对值在t之内的数。

这个题有点难度,是LeetCode Contains Duplicate II的升级版。

首先,要求距离在k之内,所以想到维护一个长度为k的滑动窗口,在这个滑动窗口内判断是否有差的绝对值在t之内的两个数。

具体参考讨论区。用一个set来保存长度为k的滑动窗口window,每次往前滑动一格,如果窗口大于k了,则删除窗口左边的元素。对于即将进入窗口的数nums[i],我们需要判断窗口内是否存在一个x,使得|x-nums[i]|\leq t,展开就是nums[i]-t\leq x\leq t+nums[i]

由于set内部是有序的树结构,所以可以用set.lower_bound直接判断大于等于nums[i]-t的数x是否在window中。如果在的话,我们再判断是否满足x\leq t+nums[i],这个式子等价于x-nums[i]\leq t,为什么要这么写呢,因为nums[i]有可能是INT_MAX或者INT_MIN,为了防止溢出,需要把相关的操作数转换为long long。

完整代码如下:

typedef long long ll;
class Solution {
public:
	bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
		set<ll> window;
		for (int i = 0; i < nums.size(); ++i) {
			if (i > k)window.erase(nums[i - k - 1]); // 删除窗口左边的元素
			auto it = window.lower_bound(ll(nums[i]) - t); // x>=nums[i]-t
			if (it != window.end() && *it - nums[i] <= t)return true; // x<=nums[i]+t
			window.insert(nums[i]);
		}
		return false;
	}
};

本代码提交AC,用时19MS。

Leave a Reply

Your email address will not be published. Required fields are marked *