LeetCode 16. 最接近的三数之和
程序员文章站
2022-06-06 10:32:13
...
题目描述
给定一个包括 n 个整数的数组 nums
和 一个目标值 target
。找出 nums
中的三个整数,使得它们的和与 target
最接近。返回这三个数的和。假定每组输入只存在唯一答案。
例如,给定数组 nums = [-1,2,1,-4], 和 target = 1.
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
思路
总体思路详见
LeetCode 15. 三数之和的思路2;
先排序(从小到大),然后以每一个数为起始,在它的右边通过两个指针left
和right
去遍历。
这里可以用min_diff
保存三个数之和sum
与target
的差的绝对值的最小值, diff
存储当前的差的绝对值;
那么,当diff <= min_diff
时,说明当前三个数之和sum
是目前最接近target
的。 应该更新min_diff
,更新clo_num(保存最靠近target的sum的值)
代码
int threeSumClosest(vector<int>& nums, int target) {
int nums_sz = nums.size();
int clo_num; // 最靠近target的sum的值
int left, right;
int sum; // 存储当前的sum
int min_diff = 9999999999; // 存储最小的差绝对值
int flag = 0; // 循环可以提前退出的条件为flag == 1
sort(nums.begin(), nums.end());
for (int i = 0; i < nums_sz - 2; i++){
if (flag == 1) // 如果存在sum==target的情况,则退出(在数组中找得到三个数使得它们的和等于target,也就是距离与target最近)
break;
left = i + 1;
right = nums_sz - 1;
// 当nums[i] == nums[i - 1]时,nums[i-1]与nums[i+1]--nums[nums_sz-1]的组合情况 和 nums[i]的情况一致,
// 因此可以跳过nums[i]的循环,i>0保证i-1不会访问越界
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
while (left < right){
sum = nums[i] + nums[left] + nums[right];
int diff = abs(sum - target); // 当前的sum与target的差值
if (diff <= min_diff){ // 当diff≤之前的最小的diff时,说明当前的sum更加靠近target,这里要有等于的情况,否则当输入为[1,1,1,1]时,进行第二次遍历的时候会有死循环
min_diff = diff;
clo_num = sum;
}
if (sum == target){ // 如果有遍历到sum与target相等的情况,则说明可以退出整个循环了
flag = 1;
break;
}
if (sum < target) { // 如果sum<target,说明nums[left]数值小了,left++
left++;
while (left < right && nums[left] == nums[left - 1]){ // 如果nums[left] == nums[left - 1](left变化之前),那么此时nums[left]--nums[right]这个范围得到的结果还是和nums[left-1]--nums[right]得到的一样
left++;
}
}
if (sum > target){ // 如果sum>target,说明nums[right]数值大了,right--
right--;
while (left < right && nums[right] == nums[right + 1]){ // 同上
right--;
}
}
}
}
return clo_num;
}
运行结果
上一篇: java 使用for循环输出九九乘法表
下一篇: Springboot常用注解