[数据结构与算法]【排序篇】【中等】leetcode第15题 三数之和

//1.枚举
//2.先排序，再分情况。（该三元单位存在两种可能；两负一非负   一负两非负） 
// 注意到题目中不能重复的要点，而单纯枚举不好解决重复问题，故考虑用第二种思路
void merge(int A[],int n,int left,int right,int mid,int* L,int* R){
    int n1=mid-left;
    int n2=right-mid;
    for(int i=0;i<n1;i++)L[i]=A[left+i];
    for(int i=0;i<n2;i++)R[i]=A[mid+i];
     	
    L[n1+1]=R[n2+1]=1000000;
    int i=0,j=0;
    for(int k=left;k<right;k++){
     	if(L[i]<=R[j]){
     	    A[k]=L[i++];
		}
		else{
			A[k]=R[j++];
		}
    }
}
void mergesort(int A[],int n,int left,int right,int* L,int* R){
	if(left+1<right){
		int mid=(left+right)/2;
		mergesort(A,n,left,mid,L,R);
		mergesort(A,n,mid,right,L,R);
		merge(A,n,left,right,mid,L,R);
	}
}
//归并排序
 
int binarysearch(int A[],int key,int left,int right){
	int mid,flag=0;
	while(left<right){
        mid=(left+right)/2;
        if(A[mid]>key){
        	right=mid;
		}
		else if(A[mid]<key){
			left=mid;
		}
		else{
			flag=1;
		}
	}
	return flag;
}
//二分搜索

int n=0,cnt=0,num=0,j;
int* L=(int*)calloc(numsSize/2+2,sizeof(int)); 
int* R=(int*)calloc(numsSize/2+2,sizeof(int));
mergesort(nums,numsSize,0,numsSize,L,R);
while(nums[n++]<0){
	cnt++;
}

for(n=0;n<cnt;n++){
	for(j=n+1;j<cnt;j++){
		while(j>n+1&&nums[j]==nums[j-1]&&j<cnt){
			j++;
		}
		if(binarysearch(nums+cnt,abs(nums[n]+nums[j]),cnt,numsSize)){
			returnColumnSizes[num][0]=nums[n];
			returnColumnSizes[num][1]=nums[j];
			returnColumnSizes[num++][2]=abs(nums[n]+nums[j]);
		}
	}
	while(nums[n]==nums[++n]);
	n--;
}
free(L);
free(R);
return returnColumnSizes;