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.
Example 1:
Input: nums = [1,2,3,1], k = 3, t = 0
Output: true
Example 2:
Input: nums = [1,0,1,1], k = 1, t = 2
Output: true
Example 3:
Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false
题意：一个数组是否存在两个元素，下标差不超过 k 同时值之差不超过 t 。
蜜汁直接遍历也能通过 不过是 O(n^2) 只能打败 10% 的提交。
两次遇到分桶法的题都没做出来 有点挫败。。。
设两个数为 a，b
满足 a - b <= t
则 (a-b) < t + 1
(a-b)/(t+1) < 1
a/(t+1) - b/(t+1) < 1
所以使用 t+1 作为大小来进行分桶，那么在一个桶的两个数一定是符合要求的，相邻的话可能是符合要求的，需要进行判断。
/**
* @param {number[]} nums
* @param {number} k
* @param {number} t
* @return {boolean}
*/
var containsNearbyAlmostDuplicate = function(nums, k, t) {
if (k < 1 || t < 0 || nums.length < 2) {
return false;
}
let bucket = {};
for (let i = 0; i < nums.length; i++) {
let index = Math.floor(nums[i] / (t + 1));
if (bucket[index] != null) return true;
if (bucket[index - 1] != null && Math.abs(bucket[index - 1] - nums[i]) <= t) {
return true;
}
if (bucket[index + 1] != null && Math.abs(bucket[index + 1] - nums[i]) <= t) {
return true;
}
bucket[index] = nums[i];
if (i >= k) {
bucket[ Math.floor(nums[i-k] / (t + 1)) ] = null;
}
}
return false;
};
之前有一点处疑惑就是一个桶如果有两个数，那么 bucket[index] = nums[i]; 后面的数字不是把前面的覆盖了么。。。后来想到既然在一个桶直接就返回true了哪有这么多事。。。
然后还有简单一点的做法，需要借助库函数，反正我写不出。。。只能用 cpp 了。。。。
#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <cmath> using namespace std; class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
set<long long> set;
for (int i = ; i < nums.size(); i++) {
// 需要找到一个数字在 [ nums[i]-t, nums[i]+t ] 之间 // >= nums[i]-t 的最小值
auto x = set.lower_bound((long long)nums[i] - t);
if (x != set.end() && abs((long long)*x - nums[i]) <= t) {
return true;
}
set.insert(nums[i]);
if (i >= k) {
set.erase(nums[i - k]);
}
}
return false;
}
};
使用 set 的 lower_bound 可以在 logn 时间内找到区间中与目标最接近数字，并判断其是否符合要求。