题目链接： 四数之和

有关题目

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在
四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？
找出所有满足条件且不重复的四元组。

示例 1：输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：输入：nums = [], target = 0
输出：[]

提示：0 <= nums.length <= 200
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9

题解

跟三数之和相类似

/*** 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().*/int cmp_int (const void* e1, const void* e2)
{return *(int*)e1 - *(int*)e2;
}
int** fourSum(int* nums, int numsSize, int target, int* returnSize, int** returnColumnSizes){*returnSize = 0;if(nums == NULL || numsSize < 4)return NULL;int first = 0,second = 0;/* 将nums排序为升序排列 */qsort(nums,numsSize,sizeof(int),cmp_int);/* 分配返回数组、返回数组的列数 */int** ret = (int**)malloc( sizeof(int*) * numsSize * numsSize);*returnColumnSizes = (int*)malloc(numsSize * numsSize * sizeof(int));//返回数组的行数for (first = 0; first < numsSize - 3; first++){//保证和上一次枚举的数字不一样if (first > 0 && nums[first - 1] == nums[first] )continue;int second = first + 1;for (;second < numsSize - 2; second++){int third = second + 1;int fourth = numsSize - 1;//保证和上一次枚举的数字不一样if (second > first + 1 && nums[second] == nums[second - 1])continue;while(third < fourth){int sum = nums[first] + nums[second] + nums[third] + nums[fourth];if ( sum == target ){ret[*returnSize] = (int*)malloc(sizeof(int) * 4);ret[*returnSize][0] = nums[first];ret[*returnSize][1] = nums[second];ret[*returnSize][2] = nums[third];ret[*returnSize][3] = nums[fourth];/* 返回数组当前行的列数为4 */(*returnColumnSizes)[*returnSize] = 4;//行数加1(*returnSize)++;//对指向c,d的指针进行去重操作while(third < fourth && nums[third] == nums[++third]);while(third < fourth && nums[fourth] == nums[--fourth]);}else if (sum < target)third++;elsefourth--;}	}}return ret;}

时间复杂度：O(N^3)
空间复杂度：O(N)