第十五题 - 三数之和

[laizimo]

题目描述

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

算法

双指针法

答案

/**
 * 双指针法
 */
var threeSum = function(nums) {
    // 数组排序 #1
    nums = nums.sort((a, b) => a - b);
    const res = [];
    let lastI, lastK;
    // 遍历数组 #2
    for (let i = 0; i < nums.length - 2; i++) {
        // 如果大于0 则返回，不会存在结果了
        if (nums[i] > 0) break;
        // 如果和上次结果一样，则跳过循环
        if (lastI === nums[i]) continue;
        // 设定两个头尾指针 #3
        let j = i + 1, k = nums.length - 1;
        while (j < k) {
            // 求和 #4
            let sum = nums[i] + nums[j] + nums[k];
            if (sum === 0) {
                // 等于0 判断前两个数字是否重复 #5
                if (lastI !== nums[i] || lastK !== nums[j]) {
                    lastI = nums[i];
                    lastK = nums[j];
                    res.push([nums[i], nums[j], nums[k]]);
                }
                // 两边缩进
                k--;
                j++;
            } else {
                // 大于0，k指针左移；小于0，k指针右移
                sum > 0 ? k-- : j++;
            }
        }
    }
    return res;
};