一、三数之和
1、题目描述
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
2、题目示例
3、题目分析
看完题目我们来简要分析一下哈。从题目我们可以提取到什么信息：
1、对一个整数数组排序
2、判断是否存在满足三数之和为0的三元组
3、对这些三元组去重，对于重复的三元组不能返回。
要求很简单，我们再来看一下给我们的函数接口是什么：
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes)
nums好理解，就是给我们的整数数组，numsSize就是数组的大小，这些都好理解，对于像博主这样的菜鸟来说，不好理解的是returnSize和returnColumnSize。这两个是什么鬼？
博主也是尝试理解了很长时间，又是找翻译，又是查资料，最后啊，感谢一位博主的文章让我恍然大悟，大家可以去看一下大佬的理解：(130条消息) 详解力扣中int *returnSize和int **returnColumnSizes_册页晚的博客-CSDN博客_*returnsize什么意思
returnSize就是你要返回有多少组三元组，这是三元组的数目；
returnColumnSize是你要返回每个三元组的数目，放在一个一维数组里面。(这个一维数组还要求你得自己动态开辟) ，通过leetcode设置的这个一维数组，大家可以感受到它是多么严谨。
求三数之和，那么我们一般的思路肯定就是三指针找满足条件的数。问题是怎么移动这三个数。
我们拿题目给的测试用例来分析：
这是找到一组各个指针走的情况。
如果我们拿一个指针i对这组数据遍历，另外两个指针left在i之后向后走，right在最后一个数，向回走。我们简单一分析就能明白，当i所指向的数大于0的时候后面就不可能有三数之和等于0.
可能有的读者要问，为什么不是大于等于0呢？因为我们要考虑一些极端情况，如果给我们这样一组数据
【0，0，0】这样显然也是满足条件的。
当然在我们还需要考虑一些问题：
1、当数组数目小于3个或者给了我们一个空指针，那么直接返回NULL。
2、我们对于去重，怎么去重？我们在去重的时候不只有指针i需要去重，left和right同样需要去重！
3、对于动态开辟的问题，博主推荐先开辟一个小的空间，比如开辟数组个大小的空间，加入判断，如果满了就扩容，这种方式比较好。
4、上代码：
int cmp(const void*x,const void* y) { return *(int*)x-*(int*)y; } int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) { *returnSize=0; if(nums==NULL||numsSize<3) return NULL; qsort(nums,numsSize,sizeof(int),cmp); int capacity=numsSize; int** triple=(int**)malloc(sizeof(int*)*capacity); *returnColumnSizes=(int*)malloc(sizeof(int)*capacity); if(triple==NULL||*returnColumnSizes==NULL) { perror("malloc fail"); exit(-1); } //要遍历的只有小于等于0的部分 for(int i=0;i<numsSize;++i) { if(nums[i]>0) break; //去重 if(i>0&&nums[i]==nums[i-1]) continue; int left=i+1; int right=numsSize-1; while(left<right) { int sum=nums[i]+nums[left]+nums[right]; if(sum==0) { int flag=1; triple[*returnSize]=(int*)malloc(sizeof(int)*3); if(triple[*returnSize]==NULL) { perror("malloc fail"); exit(-1); } triple[*returnSize][0]=nums[i]; triple[*returnSize][1]=nums[left]; triple[*returnSize][2]=nums[right]; //记录列 (*returnColumnSizes)[*returnSize]=3; (*returnSize)++; //别忘了去重 while(left<right&&nums[left]==nums[left+1]) { left++; } left++; while(left<right&&nums[right]==nums[right-1]) { right--; } right--; if(*returnSize==capacity) { //扩容 capacity*=2; int**tmp1=(int**)realloc(triple,sizeof(int*)*capacity); int*tmp2=(int*)realloc(*returnColumnSizes,sizeof(int)*capacity); if(tmp1==NULL||tmp2==NULL) { perror("realloc fail"); exit(-1); } triple=tmp1; *returnColumnSizes=tmp2; } } else if(sum<0) left++; else right--; } } return triple; }
排序推荐使用快排(qsort)，简单方便，当然希尔排序也是可以的。其他排序不太推荐，堆排序得建堆，归并空间复杂度较高。这道题目我还想说的是它可以进一步优化，不知道大家看出来没有，有一段代码特别low：
while(left<right&&nums[left]==nums[left+1]) { left++; } while(left<right&&nums[right]==nums[right-1]) { right--; } left++; right--;
这段代码可以看到非常啰嗦，它的作用是去重以及当我们找到一组之后去找下一组。
这里给大家一个小Tips，我们可以巧妙地运用判断语句前置运算算作运算的特质来设计。
while(left<right&&nums[left]==nums[++left]); while(left<right&&nums[right]==nums[--right]); //就算不满足相等，++照样会执行
这是非常巧妙的改法，就算不相等，前置++和前置--还是会执行的。但是这两端代码在leetcode上可以执行无误，但是编译器上(比如vs)可能就会出问题，这和编译器的逻辑有关。
希尔排序一遍过：
void ShellSort(int* a, int n) { int gap = n; while (gap >1) { gap = gap / 2; //插排 for (int i = 0; i < gap; i++)//gap组 { for (int j = i; j < n - gap; j += gap) { //第一个和后一个比较 int end = j; int tmp = a[end + gap]; while (end >= 0) { if (a[end] > tmp) { a[end + gap] = a[end]; end -= gap; } else break; } a[end + gap] = tmp; } } } } int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) { *returnSize=0; if(nums==NULL||numsSize<3) return NULL; ShellSort(nums,numsSize); int capacity=numsSize; int** triple=(int**)malloc(sizeof(int*)*capacity); *returnColumnSizes=(int*)malloc(sizeof(int)*capacity); if(triple==NULL||*returnColumnSizes==NULL) { perror("malloc fail"); exit(-1); } //要遍历的只有小于等于0的部分 for(int i=0;i<numsSize;++i) { if(nums[i]>0) break; //去重 if(i>0&&nums[i]==nums[i-1]) continue; int left=i+1; int right=numsSize-1; while(left<right) { int sum=nums[i]+nums[left]+nums[right]; if(sum==0) { int flag=1; triple[*returnSize]=(int*)malloc(sizeof(int)*3); if(triple[*returnSize]==NULL) { perror("malloc fail"); exit(-1); } triple[*returnSize][0]=nums[i]; triple[*returnSize][1]=nums[left]; triple[*returnSize][2]=nums[right]; //记录列 (*returnColumnSizes)[*returnSize]=3; (*returnSize)++; //别忘了去重 while(left<right&&nums[left]==nums[++left]); while(left<right&&nums[right]==nums[--right]); if(*returnSize==capacity) { //扩容 capacity*=2; int**tmp1=(int**)realloc(triple,sizeof(int*)*capacity); int*tmp2=(int*)realloc(*returnColumnSizes,sizeof(int)*capacity); if(tmp1==NULL||tmp2==NULL) { perror("realloc fail"); exit(-1); } triple=tmp1; *returnColumnSizes=tmp2; } } else if(sum<0) left++; else right--; } } return triple; }
