Netflix 观看 ID 三阶段查重：哈希、距离 K 与数值桶

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• ID 是整数；第二阶段索引距离 `|i-j|≤K`，第三阶段公开版本仅问数值差 `|a-b|≤T`，不额外沿用 K。
• T<0 或 K<0 时返回 False；如果面试官要求非法参数抛错，改输入校验。
• 第三阶段输入至少两个不同位置才可成对；相同数值在两个位置、T=0 时可返回 True。

解题路线

1. 阶段一维护已见 ID 集合，首次重复立即返回 True。
2. 阶段二记录每个 ID 最近一次出现的位置；若本次与最近位置之差≤K，即存在合格配对。只留最近位置足够，因为更早位置距离更大。
3. 阶段三令桶宽 T+1，整数 x 放入 `floor(x/(T+1))`。同桶两数差最多 T；可能合格的跨桶两数只会在相邻桶，所以检查本桶与左右邻桶并做绝对差确认。Python 的 `//` 对负数向下取整，必须用一致的 floor 规则。

手动走一遍

[1,2,3,1] 在阶段一有重复；K=2 时两个 1 距离 3，阶段二 False。阶段三 [1,5,100], T=4，1 和 5 差 4，返回 True；[-1,0], T=0，虽位于不同值桶且不相等，返回 False。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def contains_duplicate(ids):
    return len(ids) != len(set(ids))


def contains_duplicate_within_k(ids, k):
    if k < 0:
        return False
    last_seen = {}
    for index, value in enumerate(ids):
        if value in last_seen and index - last_seen[value] <= k:
            return True
        last_seen[value] = index
    return False


def contains_nearby_value(ids, threshold):
    """Published stage three has no index-distance constraint."""
    if threshold < 0:
        return False
    width = threshold + 1
    buckets = {}
    for value in ids:
        bucket = value // width
        for neighbor in (bucket - 1, bucket, bucket + 1):
            if neighbor in buckets and abs(value - buckets[neighbor]) <= threshold:
                return True
        buckets[bucket] = value
    return False

复杂度

三个阶段各一次扫描，预期时间 O(n)，哈希/桶空间 O(n)。第三阶段如果仅需判断是否存在数值差≤T，排序相邻差也可做 O(n log n) 时间、O(n) 排序空间，优点是不用讨论哈希退化和负数桶。

易错点与追问

容易失分的边界

• 把第三阶段当成标准 LC 220 同时限制 K 与 T；公开三阶段题干没有第三阶段的 K。
• T=0 时桶宽误设为 0。
• 相邻桶只看桶号，不再比较实际数值差，产生假阳性。
• 用朝零截断给负数分桶，与正数公式不一致。
• 把一篇汇总帖的所有 LC 顶题都当成独立实考样本。

继续深挖

• 如果第三阶段也加索引距离 K，怎样只保存滑动窗口内的桶并清理旧值？
• 若 ID 是 64 位，T+1 的溢出怎样处理？
• 需要返回是哪一对索引而非布尔值，桶内需保存什么？