力扣热门100题之三数之和【中等】

题目描述

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

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

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

提示：

解法1：三重for循环暴力破解

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    nums.map(num=>parseInt(num));
    nums.sort((a,b)=>a-b)
    let s=[]
    let s1=[]
    for(let i=0;i<nums.length;i++){
        for(let j=i+1;j<nums.length;j++){
            for(let k=j+1;k<nums.length;k++){
                if(nums[i]+nums[j]+nums[k]==0){
                    let arr=[nums[i],nums[j],nums[k]].sort((a,b)=>a-b);
                    let str=arr.join("")
                    if(s1.indexOf(str)==-1){
                        s.push(arr);
                        s1.push(str);
                    }
                }
            }
        }
    }
    return s
};

执行结果：

---

解法2：双指针

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    if(nums==null||nums.length<3) return [];
    nums.map(num=>parseInt(num));
    nums.sort((a,b)=>a-b)
    let s=[]
    let left=0;
    let right=0;
    for(let i=0;i<nums.length-1;i++){
        if(nums[i]>0) break;
        if(i>0&&nums[i]==nums[i-1]){
            continue;
        }else{
            left=i+1;
            right=nums.length-1;
            while(left<right){
                if(nums[i]+nums[left]+nums[right]>0){
                    //太大了 
                    right--;
                }else if(nums[i]+nums[left]+nums[right]<0){
                    //有点小
                    left++;
                }else{
                    s.push([nums[i],nums[left],nums[right]]);
                    while(left<nums.length-1&&nums[left++]==nums[left+1]){}
                    while(right>left&&nums[right--]==nums[right]){}
                }
            }
        }
    }
    return s
};

解法3：动态规划算法

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
let s=[]
let tmp=[0,0,0];
let usedIndex=[-1,-1,-1];
let str=[]
let numss=[]
var threeSum = function(nums) {
    if(nums==null||nums.length<3) return [];
    s=[]
    tmp=[0,0,0];
    usedIndex=[-1,-1,-1];
    str=[]
    nums.map(num=>parseInt(num));
    nums.sort((a,b)=>a-b)
    numss=nums;
    dfs(0)
    return s
};
function dfs(p){
    if(p==3){
        tmp=[numss[usedIndex[0]],numss[usedIndex[1]],numss[usedIndex[2]]]
        if(tmp[0]+tmp[1]+tmp[2]==0){
            tmp.sort((a,b)=>parseInt(a)-parseInt(b))
            let s1=tmp.join("")
            if(str.indexOf(s1)==-1){
                s.push([tmp[0],tmp[1],tmp[2]])
                str.push(s1)
            }
        }
        return
    }
    for(let i=0;i<numss.length;i++){
        if(usedIndex.indexOf(i)==-1){
            usedIndex[p]=i;            
            dfs(p+1);
        }
    }
}