15. 三数之和

[mengjian-github]

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

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

 

示例 1：

输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]] 示例 2：

输入：nums = [] 输出：[] 示例 3：

输入：nums = [0] 输出：[]

[mengjian-github]

最直接能想到的暴力解法是三重循环枚举，但这个问题最难的点是不重复的三元组，如果在三重循环中再去遍历之前的结果数组判断去重，是无法通过Leetcode的。

从另外一个角度去思考，如果三元组是有序的，那么枚举过程中就不会出现顺序导致的重复，比如（1，2，3）和（3，2，1），我们可以先对数组排个序，然后按枚举顺序去列举，就不会重复。 但还有另外一个问题，就是数组本身有重复元素，比如（0，0，2，4），这个时候遍历，第一个0已经遍历到了所有0开头的情况，如果下一次循环再从第二个0开始，就会导致重复，所以这里要跳过和之前已经遍历的相等的元素，判断条件是nums[i-1]===nums[i]，但要注意内层循环，第一个遍历是要保留的，下面的代码是可以通过Leetcode的暴力解法：

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    const result = [];

    nums = nums.sort((a, b) => a - b);

    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === nums[i - 1]) continue;
        for (let j = i + 1; j < nums.length; j++) {
            if (j !== i + 1 && nums[j] === nums[j - 1]) continue;
            for (let k = j + 1; k < nums.length; k++) {
                if (k !== j + 1 && nums[k] === nums[k - 1]) continue;
                const n1 = nums[i];
                const n2 = nums[j];
                const n3 = nums[k];

                const sum = n1 + n2 + n3 ;

                if (sum === 0) {
                    result.push([n1, n2, n3])
                }

            }
        }
    }

    return result;
};

[mengjian-github]

要想减除一层循环，其实思路也比较简单，就是把问题转化为两数之和，利用hashMap来消除一次循环。 不过要注意的是去重，两数之和去重需要通过hashMap的标记完成，这里采用false标记已经重复的数值对：

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    const result = [];

    nums = nums.sort((a, b) => a - b);

    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === nums[i - 1]) continue;
        // 将问题转化为两数之和的场景
        const target = 0 - nums[i];
        const map = new Map();

        for (let j = i + 1; j < nums.length; j++) {
            if (map.get(target - nums[j]) === true) {
                // 已经找到两数
                result.push([nums[i], target - nums[j], nums[j]]);
                // 此时标记为false，后续不再匹配两数，避免重复
                map.set(target - nums[j], false);
                map.set(nums[j], false);
            } else if (map.get(target - nums[j]) === false) {
                // 这个表明已经重复了，不能再set
                continue;
            } else {
                map.set(nums[j], true);
            }
        }
    }

    return result;
};