两数之和 II - 输入有序数组
两数之和 II - 输入有序数组-力扣
思路:
- 因为该数组是非递减顺序排列,因此可以设两个左右下标
- 当左右下标的数相加大于target时,则表示右下标的数字过大,因此将右下标 - -
- 当左右下标的数相加小于target时,则表示左下标的数字过小,因此将左下标 + +
- 当相等时,则将左右下标赋值给动态开辟的数组,并返回(注意左右下标要+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;
}
三数之和
三数之和-力扣
思路来源:灵茶山艾府
- 将数组进行排序
- 将三个数分为两组,第一个数一组,第二三个数的和分为一组,这样思路就和上一题的两数相加相同了
- 当第一个数存在重复时,需要continue从而跳到最后一个重复的数
- 再对后两个数进行判断,思路同第一题
这题存在两个能够进行优化的地方:
- 当三个连续数字相加大于0时,则不存在和为0的数字,可以直接break退出循环(因为数组是有序的)
- 当一个数和最后两个最大的数字之和小于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;
}