给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
方法一：
标签：数组遍历
首先对数组进行排序，排序后固定一个数 nums[i]，再使用左右指针指向 nums[i]后面的两端，数字分别为 nums[L]和 nums[R]，计算三个数的和 sum 判断是否满足为 0，
满足则添加进结果集
如果 nums[i]大于 0，则三数之和必然无法等于 0，结束循环
如果 nums[i] == nums[i−1]，则说明该数字重复，会导致结果重复，所以应该跳过
当 sum == 0 时，nums[L] == nums[L+1]则会导致结果重复，应该跳过，L++
当 sum == 0 时，nums[R] == nums[R−1] 则会导致结果重复，应该跳过，R−−
时间复杂度：O(n^2)，n 为数组长度
作者：guanpengchn
链接：https://leetcode-cn.com/problems/3sum/solution/hua-jie-suan-fa-15-san-shu-zhi-he-by-guanpengchn/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
代码实现：
int cmp(const void *a, const void *b)
{
return(*(int *)a-*(int *)b); //升序
//return(*(int *)b-*(int *)a); //降序
}
int ** threeSum(int *nums, int numsSize, int *returnSize, int **returnColumnSizes){
int *tmp_array=NULL;
int **ret_array=NULL;
int count=0;
if(numsSize == 0 || nums == NULL){
goto end;
}
qsort(nums, numsSize, sizeof(int), cmp);
tmp_array=malloc(sizeof(int)*50000);
int ii=0;
if(numsSize == 0){
goto end;
}
for(;ii<numsSize-2;ii++){
if(nums[ii] >0){
*returnSize=0;
goto end;
}
if(ii!=0 && nums[ii] == nums[ii-1]) {
continue;
}
int left=ii+1;
int right=numsSize-1;
while(left < right){
int sum=nums[ii]+nums[left]+nums[right];
if(sum==0){
if(count==0){
tmp_array[0]=nums[ii];
tmp_array[1]=nums[left];
tmp_array[2]=nums[right];
count++;
}else{
int *tmp=(char *)tmp_array+sizeof(int)*3*count;
tmp[0]=nums[ii];
tmp[1]=nums[left];
tmp[2]=nums[right];
count++;
}
while(left<right && nums[left]== nums[left+1])left++;
while(left<right && nums[right]== nums[right-1])right--;
left++;
right--;
}else if(sum <0){
left++;
}else if(sum>0){
right--;
}
}
}
end:
if(count!= 0){
*returnSize=count;
int *tmp=NULL;
tmp=malloc(sizeof(int)*count);
int ii=0;
for(;ii<count;ii++){
tmp[ii]=3;
}
*returnColumnSizes=tmp;
#if 1
ret_array=malloc(sizeof(int *) *count);
ii=0;
for(;ii<count;ii++){
ret_array[ii]=(char *)tmp_array+sizeof(int)*3*ii;
}
#endif
}else{
*returnSize=0;
*returnColumnSizes=NULL;
}
return ret_array;
}
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。