盒子
盒子
文章目录
  1. 16. 最接近的三数之和

16_最接近的三数之和_leetcode

16. 最接近的三数之和

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

例如,给定数组 nums = [-1,2,1,-4], 和 target = 1.
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

题解: 排序+双指针(leetcode15三数之和也是用该思想奥)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public int threeSumClosest(int[] nums, int target) {
if (nums == null || nums.length < 3) {
return 0;
}
Arrays.sort(nums);
int result = nums[0] + nums[1] + nums[2];
for (int i = 0; i < nums.length; i++) {
int value = nums[i];
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
int threeSum = value + nums[left]+ nums[right];
// 更新
if (Math.abs(threeSum - target) < Math.abs(result - target)) {
result = threeSum;
}
// 指针移动向目标值靠拢,大则right--,小则left++
if (threeSum > target) {
right--;
} else if (threeSum < target) {
left++;
} else {
return result;
}
}
}
return result;
}
}

AC传送门leetcode

支持一下
扫一扫,支持沈健
  • 微信扫一扫
  • 支付宝扫一扫