本周的算法題難度級(jí)別Medium,但我用了兩天閑散的時(shí)間也沒(méi)通過(guò),最后卡在了“超時(shí)”上留储，上網(wǎng)查了查，不得不欽佩大牛的想法果然牛逼，值得借鑒學(xué)習(xí)啊
題目:已知一個(gè)有n個(gè)整數(shù)的數(shù)組S曹鸠，找到所有和為0的三個(gè)數(shù)蘑志。（不允許輸出重復(fù)的解）
說(shuō)下我的思路累奈，暴力破解，把所有的組合一個(gè)一個(gè)找卖漫，找出復(fù)合要求的三個(gè)數(shù)記錄费尽，然后刪除重復(fù)的，最后剩下的就是答案羊始，需要注意的一個(gè)問(wèn)題就是關(guān)于內(nèi)存的旱幼，代碼的注釋我會(huì)寫(xiě)的詳細(xì)一些，把我遇到的坑都列出來(lái)突委，避免重復(fù)踩坑柏卤，還要說(shuō)的一點(diǎn)是這個(gè)代碼并沒(méi)有通過(guò)全部測(cè)試冬三，再倒數(shù)第二組的時(shí)候就超時(shí)了，把樣本考出來(lái)缘缚，在Xcode上運(yùn)行沒(méi)有問(wèn)題勾笆，樣本有3000個(gè)數(shù)，大概有1W多個(gè)符合要求的集合桥滨，在網(wǎng)上運(yùn)行算法的時(shí)候大概找出約3000個(gè)集合就超時(shí)了窝爪，很無(wú)奈，如下圖：
結(jié)果
接下來(lái)看看代碼：
/**
* Return an array of arrays of size *returnSize.將長(zhǎng)度返回給returnSize
* Note: The returned array must be malloced, assume caller calls free().返回的數(shù)組需要自己開(kāi)辟內(nèi)存空間齐媒，不需要考慮釋放問(wèn)題
*/
int** threeSum(int* nums, int numsSize, int* returnSize) {
//由于找不到好的容器蒲每，我就用鏈表了，也算復(fù)習(xí)一下
struct Node {
int data[3];
struct Node *next;
}node;
int i,j,k;
struct Node *head, *p, *pt;
int len = 0;
head = (struct Node *)malloc(sizeof(node));
head->next = NULL;
p = head;
//將其所有的組合一個(gè)一個(gè)列舉出來(lái)喻括，找出符合要求的所有的組合
for (i = 0; i < numsSize; i++) {
for (j = i+1; j < numsSize; j++) {
if (j == i) continue;
for (k = j+1; k < numsSize; k++) {
if (k == i || k == j) continue;
if (nums[i] + nums[j] + nums[k] == 0) {
int x1 = nums[i],x2 = nums[j],x3 = nums[k],t;
//將找出的組合進(jìn)行排序
if(x1>x2) {t=x1;x1=x2;x2=t;}
if(x2>x3) {t=x2;x2=x3;x3=t;}
if(x1>x2) {t=x1;x1=x2;x2=t;}
//記錄長(zhǎng)度
len++;
//將排序好的組合通過(guò)鏈表記錄
pt = (struct Node *)malloc(sizeof(node));
pt->data[0] = x1;
pt->data[1] = x2;
pt->data[2] = x3;
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--;//記錄長(zhǎng)度
}else pre = pre->next;
}
p = p->next;
}
//返回長(zhǎng)度
*returnSize = len;
//將最后的結(jié)果整理返回
p = head->next;
//開(kāi)辟一個(gè)二維指針邀杏，由于是指針，所有sizeof里面是int*而不是int唬血，寫(xiě)int會(huì)提示對(duì)齊問(wèn)題而報(bào)錯(cuò)
int **returnPtr = malloc(sizeof(int*) *len);
int x = 0;
while (p != NULL) {
int *arr = malloc(sizeof(int) *3);
for (i = 0;i < 3;i++)
arr[i] = p->data[i];
returnPtr[x++] = arr;
p = p->next;
}
return returnPtr;
}
好遺憾因?yàn)槌瑫r(shí)沒(méi)過(guò)望蜡，看了網(wǎng)上的思路，不禁拍手叫絕啊
/**
* 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** threeSum(int* nums, int numsSize, int* returnSize) {
int i,sum,top=-1,begin,end;
int** res=(int**)malloc(sizeof(int*)*(numsSize*(numsSize-1)*(numsSize-2))/6);
if(numsSize<3){
*returnSize=0;
return res;
}
//將nums從小到大進(jìn)行排序
quickSort(nums,0,numsSize-1);
for(i=0;i<numsSize;i++){
//從左到右(從小到大)取出一個(gè)負(fù)數(shù)
if(nums[i]>0)break;
if(i>0 && nums[i]==nums[i-1])continue;
//分別找出比這個(gè)負(fù)數(shù)大的最大的數(shù)end和最小的數(shù)begin
begin=i+1;end=numsSize-1;
//最小的數(shù)begin比最大的數(shù)小end
while(begin<end){
sum=nums[i]+nums[begin]+nums[end];
if(sum==0){
//記錄長(zhǎng)度
top++;
res[top]=(int*)malloc(sizeof(int)*3);
res[top][0]=nums[i];res[top][1]=nums[begin];res[top][2]=nums[end];
begin++;end--;
while(begin<end && nums[begin]==nums[begin-1])begin++;
while(begin<end && nums[end]==nums[end+1])end--;
}else if(sum>0) end--;//如果和大于0拷恨，則將最大的數(shù)縮小
else begin++;//如果和小于0脖律，則將最小的數(shù)擴(kuò)大
}
}
*returnSize=top+1;
return res;
}
概括一下就是先將樣本數(shù)組從小到大排序，然后遍歷找出符合要求的集合進(jìn)行返回即可挑随，因?yàn)檫M(jìn)行了排序呢状您，所以避免了重復(fù)的問(wèn)題，也通過(guò)正負(fù)數(shù)才能得出0的條件進(jìn)行了剪枝兜挨，大大提高了效率膏孟，通過(guò)各語(yǔ)言的對(duì)比，C語(yǔ)言的效率還是遙遙領(lǐng)先拌汇，就是感覺(jué)不方便柒桑。。噪舀。
