220. 存在重复元素 III

题目链接（困难）

题目描述

给你一个整数数组 nums 和两个整数 indexDiff 和 valueDiff。

找出满足下述条件的下标对 (i, j)：

• i != j
• abs(i - j) <= indexDiff
• abs(nums[i] - nums[j]) <= valueDiff

如果存在，返回 true；否则，返回 false。

数据范围：

• 2 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9
• 1 <= indexDiff <= nums.length
• 0 <= valueDiff <= 10^9

示例

示例 1：

输入： nums = [1,2,3,1], indexDiff = 3, valueDiff = 0
输出： true
解释： 取 (i, j) = (0, 3)：

• i != j ✓
• abs(0 - 3) = 3 <= 3 ✓
• abs(1 - 1) = 0 <= 0 ✓

示例 2：

输入： nums = [1,5,9,1,5,9], indexDiff = 2, valueDiff = 3
输出： false
解释： 所有下标对都不满足条件。

核心思路

两个条件：

1. 下标差 <= indexDiff：可以用长度为 indexDiff + 1 的滑动窗口维护；
2. 值差 <= valueDiff：需要在窗口内快速找到「是否存在某个数与当前数之差 ≤ valueDiff」。

滑动窗口 + 有序集合：

• 维护一个大小不超过 indexDiff + 1 的窗口；
• 用有序集合 SortedList 存窗口内的值；
• 对每个新元素 x，在有序集合中二分查找第一个 >= x - valueDiff 的元素；
• 若这个元素 <= x + valueDiff，说明存在满足条件的数，返回 true；
• 否则把 x 加入集合，若集合大小超过 indexDiff + 1，移除最旧的元素。

进阶：桶排序 $O(n)$：

• 把值域按 valueDiff + 1 分桶；
• 若两个数落在同一个桶，它们之差一定 <= valueDiff；
• 若落在相邻桶，检查具体差值是否 <= valueDiff；
• 窗口滑动时，维护桶的增删。

---

方法一：滑动窗口 + 有序集合

思路及解法

1. 用 SortedList 维护当前窗口内的所有元素；
2. 对每个 i（0 <= i < n）：
   • 在 SortedList 中找第一个 >= nums[i] - valueDiff 的位置 pos；
   • 若 pos 合法且 sorted_list[pos] <= nums[i] + valueDiff，返回 True；
   • 把 nums[i] 加入 SortedList；
   • 若窗口大小超过 indexDiff，移除 nums[i - indexDiff]；
3. 遍历结束返回 False。

为什么二分找 >= x - valueDiff：

• 窗口内任意数 y 满足 |y - x| <= valueDiff ⟺ x - valueDiff <= y <= x + valueDiff；
• 所以只需要找「第一个 >= x - valueDiff」的数，判断它是否 <= x + valueDiff。

代码

from sortedcontainers import SortedList

class Solution:
    def containsNearbyAlmostDuplicate(self, nums: list[int], indexDiff: int, valueDiff: int) -> bool:
        s = SortedList()

        for i, x in enumerate(nums):
            # 找第一个 >= x - valueDiff 的元素
            pos = s.bisect_left(x - valueDiff)
            if pos < len(s) and s[pos] <= x + valueDiff:
                return True

            s.add(x)
            # 窗口大小超过 indexDiff，移除最旧元素
            if i >= indexDiff:
                s.remove(nums[i - indexDiff])

        return False

复杂度分析

• 时间复杂度：$O(n \log(\text{indexDiff}))$，每次 bisect_left、add、remove 都是 $O(\log k)$，$k \le \text{indexDiff} + 1$。
• 空间复杂度：$O(\text{indexDiff})$，有序集合最多存 indexDiff + 1 个元素。

---

方法二：滑动窗口 + 桶排序（$O(n)$，推荐进阶）

思路及解法

核心观察：把值域按 valueDiff + 1 分成若干个桶。

• 桶的大小为 valueDiff + 1；
• 两个数若落在同一个桶，它们的差一定 <= valueDiff（因为桶内最大值减最小值 ≤ valueDiff）；
• 两个数若落在相邻桶，需要具体检查差是否 <= valueDiff；
• 两个数若落在隔一个或更远的桶，差一定 > valueDiff，不用检查。

桶的编号：bucket_id = x // (valueDiff + 1)。

注意负数：Python 的 // 是向下取整，-1 // 3 = -1，1 // 3 = 0，正好相邻，不会冲突。但 C++/Java 的 / 是向零取整，负数需要特殊处理。Python 直接用 // 即可。

流程：

1. 维护一个字典 buckets，键为桶编号，值为桶内的数；
2. 对每个 i：
   • 计算 x 的桶编号 bid；
   • 若 bid 已经在 buckets 中，说明同桶有两个数，差 <= valueDiff，返回 True；
   • 检查相邻桶 bid - 1 和 bid + 1：
     • 若存在且 abs(x - buckets[bid ± 1]) <= valueDiff，返回 True；
   • 把 x 放入 buckets[bid]；
   • 若窗口大小超过 indexDiff，移除 nums[i - indexDiff] 对应的桶。

代码

class Solution:
    def containsNearbyAlmostDuplicate(self, nums: list[int], indexDiff: int, valueDiff: int) -> bool:
        buckets = {}
        size = valueDiff + 1       # 桶的大小

        for i, x in enumerate(nums):
            bid = x // size        # 桶编号（Python 的 // 对负数也是向下取整）

            # 同桶：差值一定 <= valueDiff
            if bid in buckets:
                return True

            # 检查相邻桶
            if bid - 1 in buckets and abs(x - buckets[bid - 1]) <= valueDiff:
                return True
            if bid + 1 in buckets and abs(x - buckets[bid + 1]) <= valueDiff:
                return True

            buckets[bid] = x

            # 窗口大小超过 indexDiff，移除最旧元素
            if i >= indexDiff:
                old = nums[i - indexDiff]
                del buckets[old // size]

        return False

复杂度分析

• 时间复杂度：$O(n)$，每个元素最多操作常数次。
• 空间复杂度：$O(\text{indexDiff})$，桶最多存 indexDiff + 1 个元素。

---

两种方法对比

方法	时间	空间	特点
有序集合	$O(n \log(\text{indexDiff}))$	$O(\text{indexDiff})$	思路直观，依赖第三方库
桶排序	$O(n)$	$O(\text{indexDiff})$	最优解，面试进阶

推荐：

• 面试开场：先讲有序集合，思路自然，容易理解；
• 追问优化：再讲桶排序，展示对值域分桶的理解，时间 $O(n)$ 最优。

---

关键细节

1. 为什么有序集合只需找 >= x - valueDiff

窗口内任意数 y 满足 |y - x| <= valueDiff ⟺ x - valueDiff <= y <= x + valueDiff。

在有序集合中找第一个 >= x - valueDiff 的数：

• 若它 <= x + valueDiff，说明存在满足条件的数；
• 若它 > x + valueDiff，说明所有 >= x - valueDiff 的数都太大，不存在满足条件的数；
• 若不存在（pos == len(s)），也不存在。

2. 为什么桶的大小是 valueDiff + 1

同一个桶内任意两个数的差最大是 valueDiff（从 bid * size 到 bid * size + size - 1，差为 size - 1 = valueDiff）。

所以同桶两个数一定满足 |差| <= valueDiff，可以直接返回 True。

3. 为什么只检查相邻桶

若两个桶编号差 >= 2，桶内数值范围至少相差 size = valueDiff + 1，即两个数之差至少 > valueDiff，不可能满足条件。

4. 负数的桶编号

Python 的 // 是向下取整：

• -1 // 3 = -1；
• 1 // 3 = 0；
• -4 // 3 = -2。

所以 -1 和 1 的桶编号分别是 -1 和 0，是相邻的，逻辑正确。

C++ / Java 注意：/ 是向零取整，-1 / 3 = 0，和 1 / 3 = 0 同桶，会误判。需要写成 (x - min_val) / size 或特殊处理负数。

5. 窗口移除时的坑

移除最旧元素时，用 old // size 找到它的桶编号并删除。注意：同一个桶在窗口内最多只有一个元素（因为同桶会立即返回 True），所以直接 del buckets[bid] 是安全的。

6. valueDiff = 0 的情况

桶大小为 1，每个整数单独一个桶。同桶即相等，相邻桶差 1 > 0，不满足。等价于「窗口内是否存在相等元素」，正确。

7. 与 LC 219 存在重复元素 II 的关系

• LC 219：判断窗口内是否有相等元素（valueDiff = 0 的特例）；
• LC 220：判断窗口内是否有差 ≤ valueDiff 的元素。

LC 219 可以用哈希集合，LC 220 需要有序集合或桶排序。

---

总结

• 核心转化：|nums[i] - nums[j]| <= valueDiff ⟺ 存在 y 使 nums[i] - valueDiff <= y <= nums[i] + valueDiff；
• 滑动窗口：维护大小 indexDiff + 1 的窗口；
• 有序集合：二分找 >= x - valueDiff 的第一个元素，$O(n \log k)$；
• 桶排序：按 valueDiff + 1 分桶，同桶直接命中，相邻桶具体检查，$O(n)$；
• 易错点：
  • 负数桶编号在 Python 中直接用 // 是对的，C++/Java 需特殊处理；
  • 窗口移除时用 old // size 找桶；
• 通用套路：「窗口内值差约束」→ 有序集合二分 / 分桶。

相关题目

• LC 219. 存在重复元素 II（valueDiff = 0 的特例）
• LC 217. 存在重复元素（无窗口限制）
• LC 1438. 绝对差不超过限制的最长连续子数组（滑动窗口 + 单调队列）
• LC 239. 滑动窗口最大值（单调队列）