存在重复元素 III 图解题解

这道题到底在问什么

输入

nums=[10,4,7,1,9,3], indexDiff=2, valueDiff=2

输出

true(7 与 9)

输入

nums=[1,5,9,1,5,9], indexDiff=2, valueDiff=3

输出

false

最优解：一步一步想明白

1. 3记住「窗口管下标、有序集合管数值」,下面每帧都在套它。
2. 4开扫前窗口是空的。指针从下标 0 起一位一位往右走,先在有序窗口里查有没有数值够近的邻居,没有就把自己加进去,窗口太长就把最老的挤掉。
3. 5轮到下标 0,值是 10。先看它跟「有序窗口」里那批最近的数比,有没有谁跟它数值挨得够近。
4. 6把「值差 ≤ 2」翻译成区间:只要窗口里有数落在 [8, 12] 之间,就算找到。问题变成「窗口里有没有数在这个区间里」。
5. 7在有序窗口里找第一个不小于 8 的值:一个也没有。这一位找不到合格邻居,那就把它自己加进窗口,留给后面的数来比。
6. 8把 10 按数值大小插到窗口里的正确位置,窗口始终保持有序,这样下次二分查找才快。现在窗口里是 { 10 }。
7. 9轮到下标 1,值是 4。先看它跟「有序窗口」里那批最近的数比,有没有谁跟它数值挨得够近。
8. 10把「值差 ≤ 2」翻译成区间:只要窗口里有数落在 [2, 6] 之间,就算找到。问题变成「窗口里有没有数在这个区间里」。
9. 11在有序窗口里找第一个不小于 2 的值:是 10,可惜它大于 6、没落进区间。这一位找不到合格邻居,那就把它自己加进窗口,留给后面的数来比。
10. 12把 4 按数值大小插到窗口里的正确位置,窗口始终保持有序,这样下次二分查找才快。现在窗口里是 { 4, 10 }。
11. 13轮到下标 2,值是 7。先看它跟「有序窗口」里那批最近的数比,有没有谁跟它数值挨得够近。
12. 14把「值差 ≤ 2」翻译成区间:只要窗口里有数落在 [5, 9] 之间,就算找到。问题变成「窗口里有没有数在这个区间里」。
13. 15在有序窗口里找第一个不小于 5 的值:是 10,可惜它大于 9、没落进区间。这一位找不到合格邻居,那就把它自己加进窗口,留给后面的数来比。
14. 16把 7 按数值大小插到窗口里的正确位置,窗口始终保持有序,这样下次二分查找才快。现在窗口里是 { 4, 7, 10 }。
15. 17窗口只能装最近 2 个,现在多了一个,得把最老的那位、也就是下标 0 的 10 从有序窗口里删掉。这样窗口里永远只剩跟当前下标够近的数,「下标差 ≤ 2」这个条件就自动守住了。
16. 18轮到下标 3,值是 1。先看它跟「有序窗口」里那批最近的数比,有没有谁跟它数值挨得够近。
17. 19把「值差 ≤ 2」翻译成区间:只要窗口里有数落在 [-1, 3] 之间,就算找到。问题变成「窗口里有没有数在这个区间里」。
18. 20在有序窗口里找第一个不小于 -1 的值:是 4,可惜它大于 3、没落进区间。这一位找不到合格邻居,那就把它自己加进窗口,留给后面的数来比。
19. 21把 1 按数值大小插到窗口里的正确位置,窗口始终保持有序,这样下次二分查找才快。现在窗口里是 { 1, 4, 7 }。
20. 22窗口只能装最近 2 个,现在多了一个,得把最老的那位、也就是下标 1 的 4 从有序窗口里删掉。这样窗口里永远只剩跟当前下标够近的数,「下标差 ≤ 2」这个条件就自动守住了。
21. 23轮到下标 4,值是 9。先看它跟「有序窗口」里那批最近的数比,有没有谁跟它数值挨得够近。
22. 24把「值差 ≤ 2」翻译成区间:只要窗口里有数落在 [7, 11] 之间,就算找到。问题变成「窗口里有没有数在这个区间里」。
23. 25有序窗口里第一个不小于 7 的是 7,它正好 ≤ 11,落在区间里!这就找到了一对:下标 2 的 7 和下标 4 的 9,下标差和值差都达标,直接返回 true。
24. 26回头看整趟:窗口始终只留最近 2 个数、且保持有序;每来一个数,只用一次「找 ≥ x−2 的第一个值」的查找就判完了「有没有够近的邻居」。下标用窗口管、数值用有序集合管,一遍线性扫加每步 O(log k) 查找,就把答案找了出来。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List
from bisect import bisect_left, insort
class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:
        window = []
        for i, x in enumerate(nums):
            j = bisect_left(window, x - valueDiff)
            if j < len(window) and window[j] <= x + valueDiff:
                return True
            insort(window, x)
            if i >= indexDiff:
                old = nums[i - indexDiff]
                window.pop(bisect_left(window, old))
        return False

#include <set>
#include <vector>
using namespace std;
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;
    }
};

import java.util.*;
class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
        TreeSet<Long> set = new TreeSet<>();
        for (int i = 0; i < nums.length; i++) {
            long x = nums[i];
            Long y = set.ceiling(x - valueDiff);
            if (y != null && y <= x + valueDiff) return true;
            set.add(x);
            if (i >= indexDiff) set.remove((long) nums[i - indexDiff]);
        }
        return false;
    }
}

复杂度

面试官可能追问