0220. Contains Duplicate III =========================== 题目信息 -------- :题号: 0220. 存在重复元素 III :难度: Hard :主题: 滑动窗口、有序集合、区间查询、整数溢出 :原题: `LeetCode 0220 `_ :重点: 下标和值的双重限制、闭区间查询、窗口顺序、宽整数运算 题目重述 -------- 给定整数数组 ``nums``、非负整数 ``indexDiff`` 和 ``valueDiff``,判断是否存在不同下标 ``i``、``j``,同时满足: .. code-block:: text |i - j| <= indexDiff |nums[i] - nums[j]| <= valueDiff 两个限制必须由同一对下标满足;只返回布尔值,不修改数组。数组值可能接近整数边界,所以差值和查询区间不能依赖 ``int`` 发生溢出后的结果。``indexDiff=0`` 时不存在可用的不同下标对。 自建示例 -------- 两个条件同时成立:``nums=[8,2,5,8]``、``indexDiff=3``、``valueDiff=0`` 返回 ``true``,首尾两个 8 同值且距离为 3。 只有值域条件看似成立:``nums=[1,4,9]``、``indexDiff=2``、``valueDiff=3`` 返回 ``false``;1 与 4 的值差合格, 但 4 与 9 的值差不合格,没有一对同时通过两个限制。 只有全局值相近但下标过远:``nums=[1,5,9,1]``、``indexDiff=2``、``valueDiff=3`` 返回 ``false``, 两个 1 的距离为 3;窗口内的值差也都至少为 4。若值为 ``INT_MIN`` 和 ``INT_MAX``,代码仍必须安全地判断它们相差很远。 C++ 实现 -------- .. code-block:: cpp #include #include class Solution { public: bool containsNearbyAlmostDuplicate(std::vector& nums, int indexDiff, int valueDiff) { if (indexDiff <= 0 || valueDiff < 0) return false; std::multiset window; for (int index = 0; index < static_cast(nums.size()); ++index) { if (index > indexDiff) { auto expired = window.find(static_cast( nums[index - indexDiff - 1])); window.erase(expired); } const long long value = nums[index]; const long long lower = value - static_cast(valueDiff); const long long upper = value + static_cast(valueDiff); auto candidate = window.lower_bound(lower); if (candidate != window.end() && *candidate <= upper) return true; window.insert(value); } return false; } }; 题解 ---- 从下标对枚举到两个可维护的范围 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 枚举所有 ``i < j`` 并同时检查两个不等式最直接,但最坏需要 ``O(n^2)`` 次比较。先按下标排序或按值排序也不能一次解决: 扫描位置增加时,合法下标集合会不断滑动;同时题目还要求在活动集合中查找一个值域邻居。 固定当前下标 ``i`` 后,旧下标只有 ``[i-indexDiff, i-1]`` 可能合法。窗口之外的元素以后只会更远,先把它们删除, 就把全局位置对压缩为活动窗口。设当前值为 ``x``,窗口中的合法旧值必须落在闭区间 ``[x-valueDiff, x+valueDiff]``;这不是哈希集合的精确相等查询,而是有序值域的范围查询。 选择有序集合后,``lower_bound(lower)`` 找到第一个不小于下界的候选:若它不存在或已经大于上界,后面的值只会更大, 整个区间内没有答案;若它不大于上界,它本身就与 ``x`` 的差值不超过 ``valueDiff``。一次查找因此取代了窗口内的线性比较。 状态不变量与操作顺序 ~~~~~~~~~~~~~~~~~~~~~ 处理 ``nums[i]`` 前,``window`` 保存且只保存下标 ``[max(0,i-indexDiff), i-1]`` 的值,每个历史位置占一个副本。 当前轮必须按以下顺序转移: 1. 若 ``i > indexDiff``,删除下标 ``i-indexDiff-1``;它已经不可能与当前或未来位置满足下标距离限制; 2. 把当前值提升为 ``long long``,形成合法值域的上下界,并在历史窗口中做 ``lower_bound``; 3. 查询失败后才插入当前值,使当前下标不会与自己配对。 删除、查询、插入的顺序分别对应“去掉过期候选”“检查两个约束的交集”“让当前元素成为未来候选”。任意调换都会改变题目定义: 先插入会制造距离 0 的自配对,提前删除会丢掉恰好距离为 ``indexDiff`` 的合法位置,晚删除会放进距离为 ``indexDiff+1`` 的旧位置。 状态走读 ~~~~~~~~ 对 ``nums=[1,5,9,1]``、``indexDiff=2``、``valueDiff=3``,删除过期位置后再做值域查询: .. list-table:: :header-rows: 1 * - 当前下标和值 - 查询前窗口 - 合法值域 - 查询结果与新状态 * - ``0:1`` - ``{}`` - ``[-2,4]`` - 无候选,插入 1 * - ``1:5`` - ``{1}`` - ``[2,8]`` - ``lower_bound(2)`` 到尾部,插入 5 * - ``2:9`` - ``{1,5}`` - ``[6,12]`` - ``lower_bound(6)`` 到尾部,插入 9 * - ``3:1`` - 删除下标 0 后为 ``{5,9}`` - ``[-2,4]`` - 没有候选,插入 1 最后一步中,值 1 仍在数组前缀里,却因下标 0 已过期而不在窗口;这说明窗口删除的是位置状态,不是数值本身的永久记录。 lower_bound 的充分性 ~~~~~~~~~~~~~~~~~~~~ 有序集合中的值按升序排列。设 ``candidate`` 是第一个不小于 ``lower`` 的值: * ``candidate`` 不存在,说明所有窗口值都小于下界; * ``candidate > upper``,说明它以及后续所有值都超过上界; * ``candidate <= upper``,它同时位于闭区间 ``[lower, upper]``,与当前值构成合法值差。 所以不需要从下界向后扫描多个值,单个迭代器就覆盖了整个值域条件。使用 ``multiset`` 是为了让每个历史位置保留一份记录, 即使窗口中出现相同值,删除一个过期下标也只删除一个副本;当前值尚未插入,因此不会把自己当成历史位置。 方案取舍与代码走读 ~~~~~~~~~~~~~~~~~~~~ 哈希集合只能处理精确相等,无法回答“是否存在落在一个闭区间内的值”。桶方法可以把值域按 ``valueDiff+1`` 分桶, 期望时间接近 ``O(n)``,但需要处理负数分桶、相邻桶检查和整数边界;主解使用有序集合,以确定性的 ``O(log w)`` 查询直接表达值域范围, 其中 ``w`` 是窗口大小,代码和不变量更直接。 删除索引写成 ``index - indexDiff - 1``,因为下标差等于 ``indexDiff`` 的位置仍属于本轮候选。边界先转换到 ``long long`` 再相减或相加, 而不是先在 ``int`` 中计算后转换;这样 ``INT_MIN``、``INT_MAX`` 附近的输入不会让值域方向因溢出而改变。 复杂度与边界 ~~~~~~~~~~~~ 窗口最多包含 ``w = min(n,indexDiff)`` 个历史位置。每个元素至多一次删除、一次 ``lower_bound`` 和一次插入, 每次有序集合操作为 ``O(log w)``,总时间为 ``O(n log w)``,额外空间为 ``O(w)``。``indexDiff=0`` 没有合法下标对, ``valueDiff=0`` 退化为窗口内的精确重复判断;参数非负保证区间上下界的语义正常,防御性分支仍避免异常输入进入后续运算。