文学网站开发,上海营销型网站建设价格,自己建网站需要备案吗,中国哪家做网站的公司最大[Leetcode16]最接近的三数之和
转载自leetcode https://leetcode-cn.com/problems/3sum-closest/
1.题目
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数#xff0c;使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在…[Leetcode16]最接近的三数之和
转载自leetcode https://leetcode-cn.com/problems/3sum-closest/
1.题目
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
2.解题思路
这是一道数组搜索题需要找到满足题意的三个整数并返回他们的和。
分析
idea1. 如果使用暴力遍历显然需要三重循环是不可取的。
idea2. 数组搜索常常可以使用左右指针加快搜索速度。通常使用双指针搜索会先对数据进行一次排序。
解题步骤
step1. qsort排序
step2. 假设输出应该是sum nums[a] nums[left] nums[right]升序遍历a搜索在每个a下双指针最优解
step3. 令左指针left a1 右指针right numsSize - 1。比较当前sum和target关系。
step4. 当sum小于target时需要增加左指针 left当sum大于target时需要减少右指针right--继续遍历
step5. 双指针搜索终止条件 left right。此时sum有当前a下最优解。重复 step 2 - 4。
step6. 遍历a 从 0 至 numsSize - 1。输出最优解sum
优化
该题在解题步骤上应该有很多优化思路
例如遇到sum target时直接退出遍历。
例如遇到相同数据时候可以跳过判断减少遍历次数。
例如当a right 和target差大于sum和target差时可以退出遍历。
可信
(针对于存在数据溢出风险的代码来说)由于res需要初始化为 INT_MAX 2^31 - 1。因此计算时需要定义为long型
3.算法
排序 双指针
4.C代码
int cmp(const void *a, const void *b) {return *(int *)a - *(int *)b;
}long get_abs(long num)
{return (num 0) ? num : (0 - num);
}int threeSumClosest(int* nums, int numsSize, int target){qsort(nums, numsSize, sizeof(nums[0]), cmp);int a 0, b 1, c numsSize - 1;long int sum;long int res INT_MAX;if (numsSize 3)return nums[a] nums[b] nums[c];for (a 0; a numsSize - 2; a) {if (a 0 nums[a] nums[a - 1])continue;b a 1;c numsSize - 1;while (b c) {sum nums[a] nums[b] nums[c];if (sum target) {res (get_abs(res - target) get_abs(sum - target)) ? res : sum;while (b c nums[b] nums[b]); //b;}else if (sum target) {res (get_abs(res - target) get_abs(sum - target)) ? res : sum;while (b c nums[c] nums[--c]);//c--;}else {return sum;}}}return res;
}
