【LeetCode每日一题】220. 存在重复元素 III
今日题目220题，每日一题微信交流群可以点击右下角：合作转载->联系我，备注：刷题，拉你入群。
题目：
给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。
如果存在则返回 true，不存在返回 false。
示例 1：
代码语言：javascript复制输入：nums = [1,2,3,1], k = 3, t = 0
输出：true
题解：
本题可以基于滑动窗口，可以采用桶、map、set、multiset等数据结构解决这道题目。
注意处理的时候加减操作会越界，需要转为long long处理。
滑动窗口 multiset
维护长度为k 1元素的滑动窗口，窗口内元素从左到右插入，并查询之前是否存在满足条件的元素，查找到了就返回true，否则继续移动窗口即可。
代码语言：javascript复制class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
multiset<long long> s;
int i = 0, j = 0, n = nums.size();
while (j < n) {
while (j < n && j - i <= k) {
// [nums[i] - k, nums[i] k]
auto iter = s.lower_bound((long long)nums[j] - t);
if (iter != s.end() && *iter <= (long long)nums[j] t) return true;
s.insert(nums[j ]);
}
s.erase(nums[i ]);
}
return false;
}
};
滑动窗口 桶
同上述方法维护滑动窗口，区别在于元素处理，这里采用map记录每个桶对应的元素是谁，如果已经有这个桶id了，那么就返回true，因为再次出现的元素两个一定满足<=t，而由于也在窗口内，所以满足条件直接返回true，同时还可以在周边桶会满足条件，分别是 1与-1桶的id，去检查即可。
桶id计算方法是：假设现在数据范围是[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]，t=3，那么我们需要满足[0,1,2,3]均在index=0桶，[4,5,6,7]在index=1桶，依次类推。
那如果数据范围携带负数，例如：[-7,-6,-5,-4,-3,-2,-1,0,1,2]，t=3,我们则需要[-4,-3,-2,-1]为index=-1桶，依次类推，而按照正数的计算num/(t 1)得到的0桶的范围是[-3,-2,-1,0],因此我们要得到-1桶，需要对负数右移一位这样就变成了[-3,-2,01,0]这样数据，此时计算式：(num 1)/(t 1)，此时的桶index=0，我们需要把得到-1,再减去1，便是：(num 1)/(t 1) - 1。
代码语言：javascript复制class Solution {
public:
long long w;
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
// k index
// t value
int n = nums.size();
if (n == 0) return false;
map<long long, long long> m; // id : value
w = (long long)t 1;
int i = 0, j = 0;
while (j < n) {
while (j < n && j - i <= k) {
int id = getBucketId(nums[j]);
if (m.count(id)) return true;
if (m.count(id - 1) && abs(m[id - 1] - nums[j]) <= t) return true;
if (m.count(id 1) && abs(m[id 1] - nums[j]) <= t) return true;
m[id] = nums[j ];
}
// j -i > k
m.erase(getBucketId(nums[i ]));
}
return false;
}
int getBucketId(int num) {
if (num >= 0) return num / w;
else return (num 1) / w - 1; // 向右平移一个单位得到的桶index 左移一个单位
}
};
本节完~
