本周题目难度级别Medium,但对于我来说是低于easy的,据说《剑指offer》中也有这道题。。。
题目:找出一组集合中的四个数，要求四个数的和等于target，不能有重复
看了题目就想到之前有一道从集合中找三个数，要求等于‘0’，不能有重复，我还做超时了，这次的题目就是改改代码么，所以对我来说难度级别就低于easy了，事实上我也就用了几分钟就通过了这道题，虽然效率不高。可以对比着那道题一起看传送门，下面直接上代码：
/**
* Return an array of arrays of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
//排序
void quickSort(int* nums,int first,int end){
int temp,l,r;
if(first>=end)return;
temp=nums[first];
l=first;r=end;
while(l<r){
while(l<r && nums[r]>=temp)r--;
if(l<r)nums[l]=nums[r];
while(l<r && nums[l]<=temp)l++;
if(l<r)nums[r]=nums[l];
}
nums[l]=temp;
quickSort(nums,first,l-1);
quickSort(nums,l+1,end);
}
int** fourSum(int* nums, int numsSize, int target, int* returnSize) {
//给的集合个数小于4,直接返回0
if (numsSize < 4) {
*returnSize = 0;
return 0;
}
//排序
quickSort(nums,0,numsSize-1);
//定义链表
struct Node {
int data[4];
struct Node *next;
}node;
struct Node *head, *p, *pt;
int len = 0;
head = (struct Node *)malloc(sizeof(node));
head->next = NULL;
p = head;
//找出符合条件的四个数，并用链表记录
for (int i = 0;i < numsSize - 3;i++) {
for (int j = i+1;j < numsSize - 2;j++) {
if (i == j) j++;
if (j >= (numsSize - 2)) break;
for (int k = j+1;k < numsSize - 1;k++) {
while (k == i || k == j) k++;
if (k >= (numsSize-1)) break;
for (int l = k+1;l <numsSize;l++) {
while (l == i || l == j || l== k) l++;
if (l >= numsSize) break;
if (nums[i] + nums[j] + nums[k] + nums[l] == target) {
//记录长度
len++;
//将排序好的组合通过链表记录
pt = (struct Node *)malloc(sizeof(node));
pt->data[0] = nums[i];
pt->data[1] = nums[j];
pt->data[2] = nums[k];
pt->data[3] = nums[l];
pt->next = NULL;
p->next = pt;
p = pt;
}
}
}
}
}
//删除重复的组合
p = head->next;
struct Node *pre;
while(p != NULL) {
pre = p;
while(pre->next != NULL) {
if(pre->next->data[0] == p->data[0] && pre->next->data[1] == p->data[1] && pre->next->data[2] == p->data[2]) {
pt = pre->next;
pre->next = pt->next;
free(pt);
len--;//记录长度
}else pre = pre->next;
}
p = p->next;
}
//将最后的结果整理返回
*returnSize = len;
p = head->next;
int **returnPtr = malloc(sizeof(int*) *len);
int x = 0;
while (p != NULL) {
int *arr = malloc(sizeof(int) *4);
for (int i = 0;i < 4;i++)
arr[i] = p->data[i];
returnPtr[x++] = arr;
p = p->next;
}
return returnPtr;
}
