题目描述

给你一个整数数组 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);}}
}