网站建设与维护教学课件深圳建站网站

两数之和 II - 输入有序数组

两数之和 II - 输入有序数组-力扣

思路：

1. 因为该数组是非递减顺序排列，因此可以设两个左右下标
2. 当左右下标的数相加大于target时，则表示右下标的数字过大，因此将右下标 - -
3. 当左右下标的数相加小于target时，则表示左下标的数字过小，因此将左下标 + +
4. 当相等时，则将左右下标赋值给动态开辟的数组，并返回（注意左右下标要+1）

int* twoSum(int* numbers, int numbersSize, int target, int* returnSize) {int* ret=(int*)malloc(sizeof(int)*2);*returnSize=2;int left =0,right=numbersSize-1;while(left < right){if(numbers[left] + numbers[right] == target){ret[0]=left+1;ret[1]=right+1;return ret;}else if(numbers[left] + numbers[right] > target){right--;}else{left++;}}return ret;
}

三数之和

三数之和-力扣

思路来源：灵茶山艾府

1. 将数组进行排序
2. 将三个数分为两组，第一个数一组，第二三个数的和分为一组，这样思路就和上一题的两数相加相同了
3. 当第一个数存在重复时，需要continue从而跳到最后一个重复的数
4. 再对后两个数进行判断，思路同第一题

这题存在两个能够进行优化的地方：

1. 当三个连续数字相加大于0时，则不存在和为0的数字，可以直接break退出循环（因为数组是有序的）
2. 当一个数和最后两个最大的数字之和小于0，则该数字不可能存在为0的情况，直接continue进入下一个数字的判断即可

int cmp(const void* a, const void* b){return *(int*)a-*(int*)b;}int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {qsort(nums,numsSize,sizeof(int),cmp);int** ret=(int**)malloc(sizeof(int*)*numsSize*numsSize);*returnColumnSizes=(int*)malloc(sizeof(int)*numsSize*numsSize);int m=0;for(int i=0;i<numsSize-2;i++){//跳过重复数字if(i > 0 && nums[i] == nums[i-1])continue;if(nums[i] + nums[i+1] + nums[i+2] > 0)break;//优化一if(nums[i] + nums[numsSize-1] + nums[numsSize-2] < 0)continue;//优化二int j=i+1;int k=numsSize-1;while(j < k){if(nums[i] + nums[j] + nums[k] > 0)k--;else if(nums[i] + nums[j] + nums[k] < 0)j++;else{//添加三元组int* arr=(int*)malloc(sizeof(int)*3);arr[0]=nums[i];arr[1]=nums[j];arr[2]=nums[k];ret[m]=arr;(*returnColumnSizes)[m++]=3;//跳过重复数字for(j++;j < k && nums[j] == nums[j-1];j++);for(k--;k > j && nums[k] == nums[k+1];k--);}}}*returnSize=m;return ret;
}

最接近的三数之和

最接近的三数之和-力扣

思路同第二题类似

int cmp(const void* a,const void* b) 
{return *(int*)a-*(int*)b;
}int threeSumClosest(int* nums, int numsSize, int target) {qsort(nums,numsSize,sizeof(int),cmp);int sum=nums[0]+nums[1]+nums[2];for(int i=0;i<numsSize-2;i++){int j=i+1;int k=numsSize-1;while(j < k){int tmp=nums[i]+nums[j]+nums[k];if(abs(tmp-target) < abs(sum-target))sum=tmp;if(tmp > target)k--;else if(tmp < target)j++;elsereturn sum;}}return sum;
}