写完三数之和后，本以为这题已经够难搞了，没想到今天来了波大的--四数之和！
写了一下午，分析了一下午测试用例之后，怎么都跑不过去，当时真是有点沮丧，不过后来发现自己思路错了之后，破防了
好了，不说那么多题外话了，今天给大家分享的是四数之和的题目，因为C++还处于入门，所以今天还是用C手撕leetcode！
1、题目描述
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < n a、b、c 和 d 互不相同 nums[a] + nums[b] + nums[c] + nums[d] == target
2、示例：
3、题目分析
错误思路：
①三元化一元
刚开始博主想的是能不能去掉一元，化为三元，于是我让target减去数组中每一个数形成一个中间变量TmpTarget。
其余就和三数求和一样，一个i，一个left，一个right
只不过让这三个下标所指向的数和为TmpTarget。然后对四个数去重。
乍一想好像可以，然后再一想就会发现有很多重复组。
因为i从第一个数开始遍历，然后我还让target减去每一个数，不就会出现i所指的数和它减去的数重合，这不就把一个数加了两次？这去重越去越多，逻辑出现问题😂
说明我们这个思想有问题。
②四指针遍历
博主就是用这个思路写了一下午，指针把我转得晕头转向，四个指针，不断调试，一直有测试用例过不去，然后一个一个分析，去修改代码，改的头痛，整整一下午在这个思路里打转。
这是博主分析的一部分，大致思路跟大家提一下，就是i指向第一个数，left就是i后面那个数，right就是最后一个数，然后第三个指针mid去遍历left和right之间的数，听上去可以实现，但是博主捣鼓了一下午，去重，分析示例，各种特殊情况处理，也没实现，如果有大佬能写出来，感谢分享哦！
正确思路：
这道题，用C确实不好写，它涉及到哈希表的思想（我看题解这么说的😏）。然后我们如果去用博主昨天写的三数求和，我们应用到这里，不就是在三数求和的外面再套一层循环吗？
我们来分析一下我们的步骤：
1、第一层循环是i，还记得三数取中的去重，和剪去部分区间吗？在那里因为target==0，如果nums[i]>0，那么后面不可能有两个数和nums[i]相加等于target，但是这里的target是输入值，也就是我们需要考虑到特殊情况，比如说负数：
比如说target==-5，如果我们还是原来的三数求和的思路的话，我们很容易错失一些四元组。所以，我们要想去掉，要求target>=0的情况下才可以。
2、去重不必多言，之所以博主写成
if(i>0&&nums[i]==nums[i-1]) continue;
而不是
if(nums[i]==nums[i+1]) continue;
是因为，第二种写法对于组数的缺失：
如果是这种情况，target==8的话，就会全部continue过去。
3、第二层k循环也需要进行剪去部分区间，和去重，去重和i类似，剪去区间则不太相同
if(nums[i]+nums[k]>target&&target>=0) break;
它们是两个数相加如果大于target就会结束。
4、上代码
int cmp(const void* x,const void* y) { return *(int*)x-*(int*)y; } int** fourSum(int* nums, int numsSize, int target, int* returnSize, int** returnColumnSizes) { *returnSize=0; if(nums==NULL||numsSize<4) return NULL; qsort(nums,numsSize,sizeof(int),cmp); //排序过后 int capacity=numsSize; int**Quads=(int**)malloc(sizeof(int*)*capacity); *returnColumnSizes=(int*)malloc(sizeof(int)*capacity); if(Quads==NULL||*returnColumnSizes==NULL) { perror("malloc fail"); exit(-1); } for(int i=0;i<numsSize-3;++i) { //剪枝 if(nums[i]>target&&target>=0) break; //去重 if(i>0&&nums[i]==nums[i-1]) continue; for(int k=i+1;k<numsSize-2;++k) { //二次剪枝 if(nums[i]+nums[k]>target&&target>=0) break; //二级去重 if(k>i+1&&nums[k]==nums[k-1]) continue; int left=k+1; int right=numsSize-1; while(left<right) { if((long)nums[i]+nums[k]+nums[left]+nums[right]==target) { int* tmp=(int*)malloc(sizeof(int)*4); if(tmp==NULL) { perror("malloc fail"); exit(-1); } tmp[0]=nums[i]; tmp[1]=nums[k]; tmp[2]=nums[left]; tmp[3]=nums[right]; Quads[*returnSize]=tmp; (*returnColumnSizes)[*returnSize]=4; (*returnSize)++; if(capacity==*returnSize) { //扩容 capacity*=2; int** tmp1=(int**)realloc(Quads,sizeof(int*)*capacity); int* tmp2=(int*)realloc(*returnColumnSizes,sizeof(int)*capacity); if(tmp1==NULL||tmp2==NULL) { perror("realloc fail"); exit(-1); } Quads=tmp1; *returnColumnSizes=tmp2; } //去重 while(left<right&&nums[left]==nums[left+1]) { left++; } left++; while(left<right&&nums[right]==nums[right-1]) { right--; } right--; } else if((long)nums[i]+nums[k]+nums[left]+nums[right]>target) right--; else left++; } } } return Quads; }
本来这道题够难了，但是还是不得不吐槽leetcode的严谨，给了一组这样的测试用例，需要我们考虑整型溢出越界的问题：
