思路：排序+雙指針，時間復雜度0(n^2+nlogn)。

先將數組nums升序排序，方便去重和使用雙指針。第一層for循環來枚舉第一位數，后面使用雙指針來找到第二個、第三個數即可，細節看注釋。

C++版本：

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {// 先將數組nums升序排序，方便去重和使用雙指針int n=nums.size();sort(nums.begin(),nums.end());// 答案vector<vector<int>> v;// 遍歷第一個數for(int i=0;i<n-2;i++){// 如果和前一個數重復，跳過if(i!=0&&nums[i]==nums[i-1]) continue;// 后面數之和都大于0，直接退出if(nums[i]+nums[i+1]+nums[i+2]>0) break;// 后面數之和都小于0，跳過if(nums[i]+nums[n-2]+nums[n-1]<0) continue;//雙指針，來遍歷后面兩個數int l=i+1,r=n-1;while(l<r){int sum=nums[i]+nums[l]+nums[r];if(sum<0){l++;}else if(sum>0){r--;}else{v.push_back({nums[i],nums[l],nums[r]});l++;r--;// 避免重復的數while(l<n){if(nums[l]==nums[l-1]) l++;else break;}// 避免重復的數while(r>=l){if(nums[r]==nums[r+1]) r--;else break;}}}}return v;}
};

JAVA版本：

class Solution {public List<List<Integer>> threeSum(int[] nums) {int n=nums.length;Arrays.sort(nums);List<List<Integer>> v=new ArrayList<>();for(int i=0;i<n-2;i++){if(i!=0&&nums[i]==nums[i-1]) continue;if(nums[i]+nums[i+1]+nums[i+2]>0) break;if(nums[i]+nums[n-2]+nums[n-1]<0) continue;int l=i+1,r=n-1;while(l<r){int sum=nums[i]+nums[l]+nums[r];if(sum<0){l++;}else if(sum>0){r--;}else{v.add(Arrays.asList(nums[i],nums[l],nums[r]));l++;r--;while(l<n){if(nums[l]==nums[l-1]) l++;else break;}while(r>=l){if(nums[r]==nums[r+1]) r--;else break;}}}}return v;}
}

GO版本：

func threeSum(nums []int) [][]int {n:=len(nums)slices.Sort(nums)v:=[][]int{}for i:=0;i<n-2;i++ {if i!=0 && nums[i]==nums[i-1] {continue}if nums[i]+nums[i+1]+nums[i+2]>0 {break}if nums[i]+nums[n-2]+nums[n-1] <0 {continue}l,r:=i+1,n-1for l<r {sum:=nums[i]+nums[l]+nums[r]if sum<0 {l++}else if sum>0 {r--}else{v=append(v,[]int{nums[i],nums[l],nums[r]})l++r--for l<r {if nums[l]!=nums[l-1] {break}l++}for l<r {if nums[r]!=nums[r+1] {break}r--}}}}return v
}