四数之和
注：
如果大家没做过题目两数之和、三数之和，强烈建议先去做做，也可以参考我之前写的博客，这样做这一题会事半功倍，且由于本题思路和三数之和十分类似，故对于解题思路，也不会过多讲解，有不懂的可以参考三数之和
思路
- 本题和三数之和思想类似，同样是采用双指针的方法，只是由于多了一个数，因此也要多套一层for循环
- 同样，我们要先保证数组有序，因此首先就要对数组进行排序
- 在《三数之和》中，我们使用一层for循环来遍历数组（相当于先确定第一个数a的值），然后再利用双指针right和left确定另外两个数b，c的值，然后再用a + b + c和target比较，从而确定结果集
for(i = 0; i < numsSize; i++) { int left = i + 1; int right = numsSize - 1; while(left < right) { int sum = nums[i] + nums[left] + nums[right]; if(sum > 0) right--; else if(sum < 0) left++; else { //存入数据 } } }
- 而在《四数之和》中，由于多了一个数，那么我们就要先确定两个数的值a，b，然后再利用双指针right和left确定另外两个数b，c的值，最后再用四数之和sum和target比较，确定结果集**
for(int i = 0; i < numsSize; i++) { for(int j = i + 1; j < numsSize; j++) { int left = j + 1, right = numsSize - 1; while(left < right) { //为防止溢出，故要做出相应处理 long long sum = (long long)nums[i] + nums[j] + nums[left] + nums[right]; if(sum > target) right--; else if(sum < target) left++; else { //存入数据 } } } }
- 关于去重的处理，和《三数之和》类似，故不再赘述
for(int i = 0; i < numsSize; i++) { //a的去重 if(i > 0 && nums[i] == nums[i - 1]) continue; for(int j = i + 1; j < numsSize; j++) { //b的去重 if(j > i + 1 && nums[j] == nums[j - 1]) continue; int left = j + 1, right = numsSize - 1; while(left < right) { long long sum = (long long)nums[i] + nums[j] + nums[left] + nums[right]; if(sum > target) right--; else if(sum < target) left++; else { //存入数据 //c，d的去重 while(left < right && nums[left] == nums[++left]); while(left < right && nums[right] == nums[--right]); } } } }
实现代码
/** * Return an array of arrays of size *returnSize. * The sizes of the arrays are returned as *returnColumnSizes array. * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free(). */ //排序算法 void Sort(int *nums, int numsSize) { for(int i = 0; i < numsSize - 1; i++) { int flag = 0; for(int j = 0; j < numsSize - 1 - i; j++) { if(nums[j] > nums[j + 1]) { flag = 1; int temp = nums[j]; nums[j] = nums[j + 1]; nums[j + 1] = temp; } } if(!flag) return; } } int** fourSum(int* nums, int numsSize, int target, int* returnSize, int** returnColumnSizes){ //排序 Sort(nums, numsSize); //设定最多有100组四元组 int base = 100; //分配内存 int **arr = (int **)malloc(sizeof(int *) * base); *returnColumnSizes = (int *)malloc(sizeof(int) * base); //四元组的初始值为0 *returnSize = 0; for(int i = 0; i < numsSize; i++) { //如果第一个数就大于target且第一个数大于等于0，那么四数之和肯定大于target，直接break if(nums[i] > target && nums[i] >= 0) break; //a的去重 if(i > 0 && nums[i] == nums[i - 1]) continue; for(int j = i + 1; j < numsSize; j++) { //如果(a + b > target)且(a + b >= 0)，那么四数之和肯定大于target，直接break if((long long)nums[i] + nums[j] > target && (long long)nums[i] + nums[j] >= 0) break; //b的去重 if(j > i + 1 && nums[j] == nums[j - 1]) continue; int left = j + 1, right = numsSize - 1; while(left < right) { //为防止整形溢出，故要将sum定义为long long long long sum = (long long)nums[i] + nums[j] + nums[left] + nums[right]; if(sum > target) right--; else if(sum < target) left++; else { //为存储四元组的数组分配内存 arr[*returnSize] = (int *)malloc(sizeof(int) * 4); (*returnColumnSizes)[*returnSize] = 4; //存入数据 arr[*returnSize][0] = nums[i]; arr[*returnSize][1] = nums[j]; arr[*returnSize][2] = nums[left]; arr[*returnSize][3] = nums[right]; //四元组个数加一 (*returnSize)++; //c，d去重 while(left < right && nums[left] == nums[++left]); while(left < right && nums[right] == nums[--right]); } //如果四元组个数达到初始最大值，那就要进行扩容 if((*returnSize) == base) { base *= 2; arr = (int **)realloc(arr,sizeof(int *) * base); *returnColumnSizes = (int *)realloc(*returnColumnSizes,sizeof(int) * base); } } } } //返回存储四元组的二维数组 return arr; }
