220. 存在重复元素 III
题目描述
输入整数数组 nums，以及两个整数 indexDiff 和 valueDiff。
判断是否存在一对下标 (i, j) 同时满足：i != j；两个下标的距离 abs(i - j) 不大于 indexDiff；两处数值之差 abs(nums[i] - nums[j]) 不大于 valueDiff。
存在这样的下标对时返回 true，否则返回 false。
示例 1
输入：nums = [1,2,3,1], indexDiff = 3, valueDiff = 0 输出：true
解释：取 (i, j) = (0, 3)：下标相距 3，值都为 1，差为 0，三个条件都成立。
示例 2
输入：nums = [1,5,9,1,5,9], indexDiff = 2, valueDiff = 3 输出：false
解释：检查所有下标对，没有一对能同时满足三个条件。
数据范围
2 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^91 <= indexDiff <= nums.length0 <= valueDiff <= 10^9
解题思路：桶（按值分桶 + 滑动窗口）
下标限制用滑动窗口处理：只保留最近 indexDiff 个数。值限制用分桶处理：桶宽 w = valueDiff + 1，值 x 放进编号 x // w 的桶。同一个桶里的两个数之差一定 <= valueDiff，所以窗口中每个桶最多一个数；差值 <= valueDiff 的数只可能在同桶或相邻桶，检查 3 个桶即可。
为什么正确
处理 nums[i] 之前，buckets 恰好存着 nums[max(0, i-indexDiff) .. i-1]，且每个桶至多一个数（否则早已返回 true）。
复杂度分析
时间 O(n)，额外空间 O(min(n, indexDiff))。
易错点
负数分桶要用向下取整（Python 的 //，Java 的 Math.floorDiv）。C++/Go 的整数除法向 0 截断，-1 / 4 得 0，会让 -1 与 1 落进同一个桶而误判。桶宽是 valueDiff + 1，不是 valueDiff（valueDiff 可能为 0）。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:
w = valueDiff + 1
buckets = {}
for i, x in enumerate(nums):
b = x // w
if b in buckets:
return True
if b - 1 in buckets and x - buckets[b - 1] <= valueDiff:
return True
if b + 1 in buckets and buckets[b + 1] - x <= valueDiff:
return True
buckets[b] = x
if i >= indexDiff:
del buckets[nums[i - indexDiff] // w]
return Falseclass Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
long w = (long) valueDiff + 1;
Map<Long, Long> buckets = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
long x = nums[i];
long b = Math.floorDiv(x, w);
if (buckets.containsKey(b)) {
return true;
}
if (buckets.containsKey(b - 1) && x - buckets.get(b - 1) <= valueDiff) {
return true;
}
if (buckets.containsKey(b + 1) && buckets.get(b + 1) - x <= valueDiff) {
return true;
}
buckets.put(b, x);
if (i >= indexDiff) {
buckets.remove(Math.floorDiv((long) nums[i - indexDiff], w));
}
}
return false;
}
}class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int indexDiff, int valueDiff) {
long long w = (long long)valueDiff + 1;
unordered_map<long long, long long> buckets;
auto id = [&](long long x) { return x >= 0 ? x / w : (x + 1) / w - 1; };
for (int i = 0; i < (int)nums.size(); i++) {
long long x = nums[i];
long long b = id(x);
if (buckets.count(b)) {
return true;
}
if (buckets.count(b - 1) && x - buckets[b - 1] <= valueDiff) {
return true;
}
if (buckets.count(b + 1) && buckets[b + 1] - x <= valueDiff) {
return true;
}
buckets[b] = x;
if (i >= indexDiff) {
buckets.erase(id(nums[i - indexDiff]));
}
}
return false;
}
};func containsNearbyAlmostDuplicate(nums []int, indexDiff int, valueDiff int) bool {
w := valueDiff + 1
buckets := map[int]int{}
id := func(x int) int {
if x >= 0 {
return x / w
}
return (x+1)/w - 1
}
for i, x := range nums {
b := id(x)
if _, ok := buckets[b]; ok {
return true
}
if y, ok := buckets[b-1]; ok && x-y <= valueDiff {
return true
}
if y, ok := buckets[b+1]; ok && y-x <= valueDiff {
return true
}
buckets[b] = x
if i >= indexDiff {
delete(buckets, id(nums[i-indexDiff]))
}
}
return false
}var containsNearbyAlmostDuplicate = function(nums, indexDiff, valueDiff) {
const w = valueDiff + 1;
const buckets = new Map();
for (let i = 0; i < nums.length; i++) {
const x = nums[i];
const b = Math.floor(x / w);
if (buckets.has(b)) {
return true;
}
if (buckets.has(b - 1) && x - buckets.get(b - 1) <= valueDiff) {
return true;
}
if (buckets.has(b + 1) && buckets.get(b + 1) - x <= valueDiff) {
return true;
}
buckets.set(b, x);
if (i >= indexDiff) {
buckets.delete(Math.floor(nums[i - indexDiff] / w));
}
}
return false;
};function containsNearbyAlmostDuplicate(nums: number[], indexDiff: number, valueDiff: number): boolean {
const w = valueDiff + 1;
const buckets = new Map<number, number>();
for (let i = 0; i < nums.length; i++) {
const x = nums[i];
const b = Math.floor(x / w);
if (buckets.has(b)) {
return true;
}
if (buckets.has(b - 1) && x - buckets.get(b - 1)! <= valueDiff) {
return true;
}
if (buckets.has(b + 1) && buckets.get(b + 1)! - x <= valueDiff) {
return true;
}
buckets.set(b, x);
if (i >= indexDiff) {
buckets.delete(Math.floor(nums[i - indexDiff] / w));
}
}
return false;
}其他解法
有序集合按值排序，用一次 lower_bound 就能找到窗口内离 x 最近的较大值；桶解法把值域切成宽 valueDiff+1 的桶，同桶必满足、只需再检查相邻桶，把查找降到 O(1)。
解法 2：滑动窗口 + 有序集合 时间 O(n log k)，空间 O(min(n, k))
维护一个有序集合，里面恰好是当前下标 i 之前 indexDiff 个元素。对每个 x = nums[i]，在集合中找第一个 ≥ x - valueDiff 的元素，如果它存在且 ≤ x + valueDiff，就找到了答案。然后把 x 加入集合；当 i ≥ indexDiff 时，把已经离开窗口的 nums[i - indexDiff] 移除。C++ 用 multiset、Java 用 TreeMap 计数；Python、Go、JS/TS 没有内置的有序集合，用有序数组 + 二分查找代替。
思路直接：只要求窗口内“离 x 最近”的值，不需要分桶的巧思。多一个 log 因子；用有序数组代替时插入和删除要移动元素，最坏 O(k)。
from bisect import bisect_left, insort
from typing import List
class Solution:
def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:
window = []
for i, x in enumerate(nums):
p = bisect_left(window, x - valueDiff)
if p < len(window) and window[p] <= x + valueDiff:
return True
insort(window, x)
if i >= indexDiff:
window.pop(bisect_left(window, nums[i - indexDiff]))
return Falseclass Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
TreeMap<Long, Integer> window = new TreeMap<>();
for (int i = 0; i < nums.length; i++) {
long x = nums[i];
Long c = window.ceilingKey(x - valueDiff);
if (c != null && c <= x + valueDiff) return true;
window.merge(x, 1, Integer::sum);
if (i >= indexDiff) {
long y = nums[i - indexDiff];
if (window.merge(y, -1, Integer::sum) == 0) window.remove(y);
}
}
return false;
}
}class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int indexDiff, int valueDiff) {
multiset<long long> window;
for (int i = 0; i < (int)nums.size(); i++) {
long long x = nums[i];
auto it = window.lower_bound(x - valueDiff);
if (it != window.end() && *it <= x + valueDiff) return true;
window.insert(x);
if (i >= indexDiff) window.erase(window.find(nums[i - indexDiff]));
}
return false;
}
};func containsNearbyAlmostDuplicate(nums []int, indexDiff int, valueDiff int) bool {
window := []int{}
for i, x := range nums {
p := sort.SearchInts(window, x-valueDiff)
if p < len(window) && window[p] <= x+valueDiff {
return true
}
p = sort.SearchInts(window, x)
window = append(window, 0)
copy(window[p+1:], window[p:])
window[p] = x
if i >= indexDiff {
q := sort.SearchInts(window, nums[i-indexDiff])
window = append(window[:q], window[q+1:]...)
}
}
return false
}var containsNearbyAlmostDuplicate = function(nums, indexDiff, valueDiff) {
const window = [];
const lowerBound = (v) => {
let lo = 0, hi = window.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (window[mid] < v) lo = mid + 1;
else hi = mid;
}
return lo;
};
for (let i = 0; i < nums.length; i++) {
const x = nums[i];
const p = lowerBound(x - valueDiff);
if (p < window.length && window[p] <= x + valueDiff) return true;
window.splice(lowerBound(x), 0, x);
if (i >= indexDiff) window.splice(lowerBound(nums[i - indexDiff]), 1);
}
return false;
};function containsNearbyAlmostDuplicate(nums: number[], indexDiff: number, valueDiff: number): boolean {
const window: number[] = [];
const lowerBound = (v: number): number => {
let lo = 0, hi = window.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (window[mid] < v) lo = mid + 1;
else hi = mid;
}
return lo;
};
for (let i = 0; i < nums.length; i++) {
const x = nums[i];
const p = lowerBound(x - valueDiff);
if (p < window.length && window[p] <= x + valueDiff) return true;
window.splice(lowerBound(x), 0, x);
if (i >= indexDiff) window.splice(lowerBound(nums[i - indexDiff]), 1);
}
return false;
}