題目

給你一個整數數組?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 。

解析

為方便雙指針以及跳過相同元素，先把 nums 排序。

枚舉 nums[i]，問題變成 nums[j]+nums[k]=?nums[i]。

題目要求答案中不能有重復的三元組。如何避免重復？

在外層循環中，如果發現 nums[i]=nums[i?1]，那么 nums[i] 與后面兩個數組成的和為 0 的三元組，nums[i?1] 也能組成一模一樣的三元組，這就重復了，所以遇到 nums[i]=nums[i?1] 的情況，直接 continue。

在內層循環中，當三數之和等于 0 時，為避免把相同的三元組計入答案，跳過后續相同的 nums[j] 和 nums[k]（也可以只跳過相同的 nums[j]）。

優化
優化一：如果 nums[i] 與后面最小的兩個數相加 nums[i]+nums[i+1]+nums[i+2]>0，那么后面不可能存在三數之和等于 0，break 外層循環。

優化二：如果 nums[i] 與后面最大的兩個數相加 nums[i]+nums[n?2]+nums[n?1]<0，那么內層循環不可能存在三數之和等于 0，但繼續枚舉，nums[i] 可以變大，所以后面還有機會找到三數之和等于 0，continue 外層循環。

------------------------------------------------

作者：靈茶山艾府
鏈接：https://leetcode.cn/problems/3sum/
來源：力扣（LeetCode）

答案

/*** @param {number[]} nums* @return {number[][]}*/
var threeSum = function(nums) {nums.sort((a,b) => a-b);    //排序const ans = [];const len = nums.length;for(let k=0; k<len-2; k++) {//和前一個數相同，那么后面能組成0的兩個數的答案相同，跳過該數if(k>0 && nums[k] === nums[k-1]) continue;//和后面兩個最小的數之和都大于0，不可能找到等于0的兩個數，跳出for循環if(nums[k] + nums[k+1] + nums[k+2] > 0) break;//和最后兩個最大的數之和都小于0，內層循環固定位的數太小，回到外層循環找更大的數if(nums[k] + nums[len-2] + nums[len-1] < 0) continue;let i = k+1, j=len-1;while(i < j) {const s = nums[k] + nums[i] + nums[j];if(s < 0) {    //換更大的加數i++;} else if(s > 0) {    //換更小的加數j--;} else {ans.push([ nums[k], nums[i], nums[j]]);    //等于0，加入答案for(i++; i<j && nums[i] === nums[i-1]; i++);    //跳過重復的數for(j--; j>i && nums[j] === nums[j+1]; j--);    //跳過重復的數}}}return ans;
};

復雜度分析

時間復雜度：O(n^2)，其中 n 為 nums 的長度。排序 O(nlogn)。外層循環枚舉第一個數，做法是 O(n) 雙指針。所以總的時間復雜度為 O(n^2?)。
空間復雜度：O(1)。返回值不計入。忽略排序的棧開銷。

------------------------------------------------

作者：靈茶山艾府
鏈接：https://leetcode.cn/problems/3sum/
來源：力扣（LeetCode）