給你一個整數(shù)數(shù)組?nums?，判斷是否存在三元組?[nums[i], nums[j], nums[k]]?滿足?i != j、i != k?且?j != k?，同時還滿足?nums[i] + nums[j] + nums[k] == 0?。請你返回所有和為?0?且不重復(fù)的三元組。

答案中不可以包含重復(fù)的三元組。

示例 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] 。

解析：

先對數(shù)組排序，設(shè)一非遞減的數(shù)組示例和初始三指針位置及名字如下所示。

固定i，即可轉(zhuǎn)換為尋找滿足?nums[l]+nums[r]=?nums[i]?的三元組，因為不能包含重復(fù)的三元組，以下兩個三元組只能取一個，而后我們再考慮其是否滿足?nums[l]+nums[r]=?nums[i]。

移動指針的時候，需要規(guī)避連續(xù)的重復(fù)元素

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {//排序c// 待返回的三元組vector<vector<int>> triples;for(int i = 0; i < nums.size(); i++){// 檢測重復(fù)的 nums[i]if(i > 0 && nums[i] == nums[i-1]) continue;int l = i + 1;int r = nums.size() - 1;while(l < r) {// 檢測重復(fù)的 nums[l] 并防止越界while(l > i + 1 && l < nums.size() && nums[l] == nums[l-1]) l++;// 檢測重復(fù)的 nums[r] 并防止越界while(r < nums.size() - 1 && r > i && nums[r] == nums[r+1]) r--;// 防止 l, r 錯位if(l >= r) break;if(nums[i] + nums[l] + nums[r] > 0) r--;else if(nums[i] + nums[l] + nums[r] < 0) l++;else {// nums[l] + nums[r] == nums[i], 三元組符合，添加入結(jié)果triples.push_back({nums[i], nums[l], nums[r]});l++; r--;}}}return triples;}
};

int cmp(const void* pa, const void* pb){int a=*(int*)pa;int b=*(int*)pb;return a>b?1:-1;
}
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){int base=100;//數(shù)組的初始長度，可更改//初始化處理返回值，二維數(shù)組的大小和保存每一個一維數(shù)組大小的數(shù)組的空間保持一致int** res=(int**)malloc(sizeof(int*)*base);*returnColumnSizes=(int*)malloc(sizeof(int)*base);*returnSize=0;int i,j,k;//排序qsort(nums,numsSize,sizeof(int),cmp);for(i=0;i<numsSize;i++){//先確定第三個數(shù)的值，再對剩下的兩個數(shù)進行兩數(shù)之和的操作//若本次的第三個數(shù)與上一次的情況相同，則跳過這個數(shù)if(i>0&&nums[i]==nums[i-1])continue;//給定nums[i]，以j，k作為雙指針進行兩數(shù)之和操作j=i+1;k=numsSize-1;while(j<k){int sum=nums[i]+nums[j]+nums[k];if(sum==0){//剛好遇見符合要求的三元組//申請返回值二維數(shù)組的空間res[*returnSize]=(int*)malloc(sizeof(int)*3);//每一個數(shù)組大小都為3(*returnColumnSizes)[*returnSize]=3;//給申請的空間賦值res[*returnSize][0]=nums[i];res[*returnSize][1]=nums[j];res[*returnSize][2]=nums[k];//二維數(shù)組的行數(shù)加1(*returnSize)++;//如果二維數(shù)組的大小達到初始設(shè)定的行數(shù)，則進行空間擴容if(*returnSize==base){base*=2;res=(int**)realloc(res,sizeof(int*)*base);*returnColumnSizes=(int*)realloc(*returnColumnSizes,sizeof(int)*base);}//記錄符合要求的兩個數(shù)，進行去重int num1=nums[j],num2=nums[k];while(nums[j]==num1&&j<k)j++;while(nums[k]==num2&&j<k)k--;}//若三個數(shù)之和小于0，則左邊的指針右移else if(sum<0)j++;//若三個數(shù)的之和大于0，則右邊的指針往左移else k--;}}return res;
}