题目
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：
答案中不可以包含重复的四元组。
示例：
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/4sum
思路
1、最简单的思路：暴力枚举，四个循环遍历处理；然后去重处理；
2、先排序，而后使用双指针，运算过程中去重； （1）排序 qsort； （2）两重循环之后，使用双指针； （3）去重处理原则：四个数，每个数在其数据范围内不可以遍历两次；
程序
int cmp(const void *a
, const void *b
){
return *(int*)a
- *(int*)b
;
}
int** fourSum(int* nums
, int numsSize
, int target
, int* returnSize
, int** returnColumnSizes
){
if(numsSize
< 4){
(*returnSize
) = 0;
(*returnColumnSizes
) = 0;
return NULL;
}
qsort(nums
, numsSize
, sizeof(int), cmp
);
(*returnSize
) = 0;
int maxSize
= numsSize
* numsSize
;
int** a
= (int**)malloc(sizeof(int*)*maxSize
);
(*returnColumnSizes
) = (int*)malloc(sizeof(int)*maxSize
);
int i
= 0,j
,k
,l
;
while(i
< numsSize
- 3){
j
= i
+ 1;
while(j
< numsSize
- 2){
k
= j
+ 1;
l
= numsSize
- 1;
while(k
< l
){
if(nums
[i
] + nums
[j
] + nums
[k
] + nums
[l
] < target
){
k
++;
}else if(nums
[i
] + nums
[j
] + nums
[k
] + nums
[l
] > target
){
l
--;
}else if(nums
[i
] + nums
[j
] + nums
[k
] + nums
[l
] == target
){
a
[(*returnSize
)] = (int*)malloc(sizeof(int)*4);
(*returnColumnSizes
)[(*returnSize
)] = 4;
a
[(*returnSize
)][0] = nums
[i
];
a
[(*returnSize
)][1] = nums
[j
];
a
[(*returnSize
)][2] = nums
[k
];
a
[(*returnSize
)][3] = nums
[l
];
(*returnSize
)++;
while(nums
[k
] == nums
[++k
] && k
< l
);
while(nums
[l
] == nums
[--l
] && k
< l
);
}
}
while(nums
[j
] == nums
[++j
] && j
< numsSize
- 2);
}
while(nums
[i
] == nums
[++i
] && i
< numsSize
- 3);
}
return a
;
}
