Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note: The solution set must not contain duplicate quadruplets.
For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.A solution set is:[ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2]]思路:
采用循环或者递归,逐个查找计算总和。代码一(函数循环,12ms)
/** * Return an array of arrays of size *returnSize. * Note: The returned array must be malloced, assume caller calls free(). */int** fourSum(int* nums, int numsSize, int target, int* returnSize) { int flag; int temp; int min; int **output=NULL; int last1,last2,last3,last4;//用于记录上一次取值 //用于判断是否判断此次取值与上次取值是否相同 int flag1=0; int flag2=0; int flag3=0; int flag4=0; int sizereturn=0; //先进行排序 for(int i=0;i<numsSize;i++) { min=nums[i]; for(int j=i;j<numsSize;j++) { if(min>=nums[j]) { flag=j; min=nums[j]; } } temp=nums[flag]; nums[flag]=nums[i]; nums[i]=min; } for(int i=0;i<numsSize-3;i++) { if(flag1&&nums[i]==last1)continue;//改变第一个值时不可与前一个取值相同,否则重复 if(4*nums[i]>target)break; if((nums[i]+nums[numsSize-1]+nums[numsSize-2]+nums[numsSize-3])<target)continue; flag2=0; for(int j=i+1;j<numsSize-2;j++) { if(flag2&&nums[j]==last2)continue;//改变第二个值时不可与前一个取值相同,否则重复 if((nums[i]+3*nums[j])>target)break; //排序之后,最后的值最大,如果加上最后的值仍小于target,则跳过 if((nums[i]+nums[j]+nums[numsSize-2]+nums[numsSize-1])<target)continue; flag3=0; for(int k=j+1;k<numsSize-1;k++) { if(flag3&&nums[k]==last3)continue;//改变第三个值时不可与前一个取值相同,否则重复 if((nums[i]+nums[j]+nums[k]+nums[k])>target)break; if((nums[i]+nums[j]+nums[k]+nums[numsSize-1])<target)continue; flag4=0; for(int m=k+1;m<numsSize;m++) { if(flag4&&nums[m]==last4)continue; if(nums[i]+nums[j]+nums[k]+nums[m]==target) { sizereturn++; output=(int**)realloc(output,sizereturn*sizeof(int*)); *(output+sizereturn-1)=(int*)malloc(4*sizeof(int)); output[sizereturn-1][0]=nums[i]; output[sizereturn-1][1]=nums[j]; output[sizereturn-1][2]=nums[k]; output[sizereturn-1][3]=nums[m]; } else if((nums[i]+nums[j]+nums[k]+nums[m])>target)break; flag4=1; last4=nums[m]; } flag3=1; last3=nums[k]; } flag2=1; last2=nums[j]; } flag1=1; last1=nums[i]; } *returnSize=sizereturn; return output;}代码二(递归函数,19ms)
/** * Return an array of arrays of size *returnSize. * Note: The returned array must be malloced, assume caller calls free(). */void findtarget(int* nums, int numsSize, int target,int output[],int index,int n,int ***returnarr,int *returnSize){ int flag=0; int last; if(n==1) { for(int i=index;i<numsSize-n+1;i++) { if(flag&&last==nums[i])continue; if(-1*nums[i]+target==0) { (*returnSize)++; output[n-1]=nums[i]; *returnarr=(int**)realloc(*returnarr,(*returnSize)*sizeof(int*)); *(*returnarr+(*returnSize)-1)=(int*)malloc(4*sizeof(int)); for(int j=0;j<4;j++) { (*returnarr)[*returnSize-1][j]=output[3-j]; } } last=nums[i]; flag=1; } } else { for(int i=index;i<numsSize-n+1;i++) { int sum=nums[i]; int sum2; if(flag&&last==nums[i])continue; output[n-1]=nums[i]; for(int si=numsSize-1;si>(numsSize-n);si--) sum+=nums[si]; sum2=n*nums[i]; if(sum2>target)break; if(sum<target)continue; findtarget(nums,numsSize,target-nums[i],output,i+1,n-1,returnarr,returnSize); last=nums[i]; flag=1; } }}int** fourSum(int* nums, int numsSize, int target, int* returnSize) { int output[4]; int **returnarr=NULL; int num=0; int flag=0; int last; int min; int minflag; int temp; *returnSize=0; for(int i=0;i<numsSize;i++) { min=nums[i]; for(int j=i;j<numsSize;j++) { if(min>=nums[j]) { minflag=j; min=nums[j]; } } temp=nums[minflag]; nums[minflag]=nums[i]; nums[i]=min; } findtarget(nums,numsSize,target,output,0,4,&returnarr,returnSize); return returnarr;}思路拓展:
采用递归函数稍加修改可适用于K-SUM问题
新闻热点
疑难解答