存在重复元素 III

记住「窗口管下标、有序集合管数值」,下面每帧都在套它。

开扫前窗口是空的。指针从下标 0 起一位一位往右走,先在有序窗口里查有没有数值够近的邻居,没有就把自己加进去,窗口太长就把最老的挤掉。

轮到下标 0,值是 10。先看它跟「有序窗口」里那批最近的数比,有没有谁跟它数值挨得够近。

把「值差 ≤ 2」翻译成区间:只要窗口里有数落在 [8, 12] 之间,就算找到。问题变成「窗口里有没有数在这个区间里」。

在有序窗口里找第一个不小于 8 的值:一个也没有。这一位找不到合格邻居,那就把它自己加进窗口,留给后面的数来比。

把 10 按数值大小插到窗口里的正确位置,窗口始终保持有序,这样下次二分查找才快。现在窗口里是 { 10 }。

轮到下标 1,值是 4。先看它跟「有序窗口」里那批最近的数比,有没有谁跟它数值挨得够近。

把「值差 ≤ 2」翻译成区间:只要窗口里有数落在 [2, 6] 之间,就算找到。问题变成「窗口里有没有数在这个区间里」。

在有序窗口里找第一个不小于 2 的值:是 10,可惜它大于 6、没落进区间。这一位找不到合格邻居,那就把它自己加进窗口,留给后面的数来比。

把 4 按数值大小插到窗口里的正确位置,窗口始终保持有序,这样下次二分查找才快。现在窗口里是 { 4, 10 }。

轮到下标 2,值是 7。先看它跟「有序窗口」里那批最近的数比,有没有谁跟它数值挨得够近。

把「值差 ≤ 2」翻译成区间:只要窗口里有数落在 [5, 9] 之间,就算找到。问题变成「窗口里有没有数在这个区间里」。

在有序窗口里找第一个不小于 5 的值:是 10,可惜它大于 9、没落进区间。这一位找不到合格邻居,那就把它自己加进窗口,留给后面的数来比。

把 7 按数值大小插到窗口里的正确位置,窗口始终保持有序,这样下次二分查找才快。现在窗口里是 { 4, 7, 10 }。

窗口只能装最近 2 个,现在多了一个,得把最老的那位、也就是下标 0 的 10 从有序窗口里删掉。这样窗口里永远只剩跟当前下标够近的数,「下标差 ≤ 2」这个条件就自动守住了。

轮到下标 3,值是 1。先看它跟「有序窗口」里那批最近的数比,有没有谁跟它数值挨得够近。

把「值差 ≤ 2」翻译成区间:只要窗口里有数落在 [-1, 3] 之间,就算找到。问题变成「窗口里有没有数在这个区间里」。

在有序窗口里找第一个不小于 -1 的值:是 4,可惜它大于 3、没落进区间。这一位找不到合格邻居,那就把它自己加进窗口,留给后面的数来比。

把 1 按数值大小插到窗口里的正确位置,窗口始终保持有序,这样下次二分查找才快。现在窗口里是 { 1, 4, 7 }。

窗口只能装最近 2 个,现在多了一个,得把最老的那位、也就是下标 1 的 4 从有序窗口里删掉。这样窗口里永远只剩跟当前下标够近的数,「下标差 ≤ 2」这个条件就自动守住了。

轮到下标 4,值是 9。先看它跟「有序窗口」里那批最近的数比,有没有谁跟它数值挨得够近。

把「值差 ≤ 2」翻译成区间:只要窗口里有数落在 [7, 11] 之间,就算找到。问题变成「窗口里有没有数在这个区间里」。

有序窗口里第一个不小于 7 的是 7,它正好 ≤ 11,落在区间里!这就找到了一对:下标 2 的 7 和下标 4 的 9,下标差和值差都达标,直接返回 true。

回头看整趟:窗口始终只留最近 2 个数、且保持有序;每来一个数,只用一次「找 ≥ x−2 的第一个值」的查找就判完了「有没有够近的邻居」。下标用窗口管、数值用有序集合管,一遍线性扫加每步 O(log k) 查找,就把答案找了出来。

边界:indexDiff=0 必 false、valueDiff=0 即找相等、大数差防溢出。

两个高频追问:O(n) 桶分法、以及重复值的处理。