本周題目難度級別Medium,但對于我來說是低于easy的,據(jù)說《劍指offer》中也有這道題。。。
題目:找出一組集合中的四個數(shù)贴浙，要求四個數(shù)的和等于target，不能有重復(fù)
看了題目就想到之前有一道從集合中找三個數(shù)署恍，要求等于‘0’崎溃，不能有重復(fù)，我還做超時了盯质，這次的題目就是改改代碼么袁串，所以對我來說難度級別就低于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) {
//給的集合個數(shù)小于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;
//找出符合條件的四個數(shù)破镰，并用鏈表記錄
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;
}
}
}
}
}
//刪除重復(fù)的組合
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;
}
//將最后的結(jié)果整理返回
*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;
}
