JavaScript实现Three Sum算法漏算三元组 求定位bug

问题现象 #

实现目标为查找数组内所有和为0的不重复三元组的Three Sum算法时，出现结果遗漏：

• 输入用例[-1,0,1,2,-1,-4]运行结果正常
• 输入用例[-1,0,1,2,-1,-4,-2,-3,3,0,4]时，实际输出为[[-1,-1,2],[-1,0,1],[-2,0,2],[-3,0,3],[-3,1,2],[-4,0,4],[-4,1,3]]，对比正确结果[[-4,0,4],[-4,1,3],[-3,-1,4],[-3,0,3],[-3,1,2],[-2,-1,3],[-2,0,2],[-1,-1,2],[-1,0,1]]，遗漏了[-3,-1,4]、[-2,-1,3]两个符合要求的三元组。

问题代码 #

var threeSum = function (nums) {
    const sorted = nums.sort()
    const output = []
    for (let i = 0; i < sorted.length - 2; i++)
        if (i === 0 || (i > 0 && sorted[i] !== sorted[i - 1])) {
            let lower = i + 1
            let higher = sorted.length - 1

            while (lower < higher) {
                const currentSum = sorted[i] + sorted[lower] + sorted[higher];
                if (currentSum === 0) {
                    output.push([sorted[i], sorted[lower], sorted[higher]])
                    while (sorted[lower] === sorted[lower + 1]) lower++
                    while (sorted[higher] === sorted[higher - 1]) higher--
                    lower++
                    higher--
                }

                else if (currentSum < 0) {
                    lower++
                } else {
                    higher--
                }
            }
        }
    }
    return output
 };

故障原因 #

Bug出在数组排序逻辑：JavaScript原生Array.sort()默认按照字符串Unicode编码顺序排序，而非数值大小排序。
对问题用例执行默认排序后，得到的数组为[-1, -1, -2, -3, -4, 0, 0, 1, 2, 3, 4]，负数区段顺序完全混乱，后续基于有序数组设计的双指针遍历逻辑自然会跳过合法的三元组组合。

修复方法 #

给sort()方法传入数值比较函数，保证数组按数值升序排列即可，其余双指针、去重逻辑均正常可用。
将排序行：

const sorted = nums.sort()

修改为：

const sorted = nums.sort((a, b) => a - b)

修改后排序结果为[-4, -3, -2, -1, -1, 0, 0, 1, 2, 3, 4]，运行即可得到全部正确结果。

内容的提问来源于stack exchange，提问作者Leo Troper