题目描述

3Sum

给定一个数字数组 n ，判断 n里是否存在三个数 a, b, c 满足 a+b+c=0 找出所有满足该情况的三元组。

示例1：

Input: [-1, 0, 1, 2, -1, -4]
Output: [
  [-1, 0, 1],
  [-1, -1, 2]
]

From leetcode No.15 Medium (opens new window)

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

};

解法

点击查看

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
const threeSum = function(nums) {
    const sorted_nums = Array.from(nums).sort((a, b)=>a-b)
    const ret = []
    for(let i=0; i<sorted_nums.length-2; i++){
        if(sorted_nums[i] > 0)
            break;
        if(i !== 0 && sorted_nums[i] === sorted_nums[i-1])
            continue;
        let left = i+1
        let right = sorted_nums.length - 1
        const sum = 0 - sorted_nums[i]
        while(left < right){
            while(left !== i+1 && sorted_nums[left] === sorted_nums[left-1])
                left++;
            while(right !== sorted_nums.length - 1 && sorted_nums[right] === sorted_nums[right+1])
                right--;
            if(left >= right)
                break;
            if(sorted_nums[left] + sorted_nums[right] === sum){
                ret.push([sorted_nums[i], sorted_nums[left], sorted_nums[right]])
                left++;
                right--;
            }
            else if(sorted_nums[left] + sorted_nums[right] < sum){
                left++;
            }
            else{
                right--;
            }
        }
    }
    return ret
};

总结

• 题目在 2sum基础上做了升级，元素不再唯一，结果也不唯一，且要找出所有不重复情况
• 元素不唯一，所以哈希的策略行不通
• 要找出三个数，如果确定一个数，寻找另外两个数就变成了 2sum的情况, 使用左右指针比对结果
• 因为结果需要去重，所以左中右三个数不能与对应的前一个相同，相同则继续偏移
• 又因为需要找出所有结果，所以当找出符合条件的结果后，需要同时移动左右指针继续循环