Meta 3Sum：排序双指针与两层去重

题意与假设

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

• 输出唯一value triples，三个位置必须不同，输入可重复，复制排序不改原输入；目标0。

解题路线

1. 排序后固定a[i]，在后缀left/right找pair sum=−a[i]。total小增left、total大减right，由排序单调性安全排除一行候选。
2. 固定值与上一个相同则跳过，避免同first value重复答案；命中后跳过两侧同值runs，防同一个三元组多次输出。
3. 去重不等于输入先set。[-1,-1,2]需要两个不同位置−1，输入set会错误丢掉有效三元组。
4. i<left<right确保位置不同。a[i]>0后全后缀非负，不可能再和0，可提前结束；全零时仍输出(0,0,0)一次。
5. 三元组排序后按固定first顺序输出，独立oracle枚举所有位置组合再归一value tuple，可检查去重与重数。

手动走一遍

[-1,0,1,2,-1,-4]返回(-1,-1,2)、(-1,0,1)。[0,0,0,0]只一个(0,0,0)；[−1,2]少于3位置无结果。

Python 参考实现

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

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

def three_sum(values):
    """Unique value triples summing to zero; returns sorted triples, input copied."""
    a=sorted(values);result=[]
    for i in range(len(a)-2):
        if i and a[i]==a[i-1]:continue
        if a[i]>0:break
        left=i+1;right=len(a)-1
        while left<right:
            total=a[i]+a[left]+a[right]
            if total<0:left+=1
            elif total>0:right-=1
            else:
                result.append((a[i],a[left],a[right]));x,y=a[left],a[right]
                while left<right and a[left]==x:left+=1
                while left<right and a[right]==y:right-=1
    return result

复杂度

O(N²)扫描加O(N log N)排序，当前O(N)排序复制空间、结果O(T)；固定i内双指针各最多N步，不是三重O(N³)。

易错点与追问

容易失分的边界

• 输入set消掉构成三元组所需重数。
• 命中只移动一侧可能重复输出或死循环。

继续深挖

• 任意target只需比较total与target，但a[i]>0提前终止不再普遍成立。
• 如果输出所有index triples，值去重政策要取消，结果数量可达O(N³)。