Leetcode之16-最接近的三数之和(3Sum Closest)

算法题

题干

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。例如,给定数组 nums = [-1,2,1,-4], 和 target = 1。与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

解法

本题同样比较简单, 第一步就是排序, 排序后采用双指针才更方便向中间靠拢。与三数之和思路一样, 唯一的区别是本道算法题需要两个变量用来存储差与和。

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int minDiff = Integer.MAX_VALUE, data = 0;
final int LEN = nums.length;
for (int i = 0; i < LEN - 2; i++) {
int left = i + 1, right = LEN - 1;
while(left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == target) {
return target;
}
if (Math.abs(sum - target) < minDiff) {
minDiff = Math.abs(sum - target);
data = sum;
}
if (sum > target) {
right--;
} else {
left++;
}
}
}
return data;
}

代码解析

  1. 第3行代码中变量minDiff表示最小差值, data表示三数之和。
  2. 第5行代码for循环中i<LEN-2表示外层循环到倒数第三个数即可, 毕竟题目找三数之和。
  3. 第7行代码while循环表示双指针left和right向中间靠拢。
  4. 剩余代码表示如果和sum恰好等于三数之和即直接返回, 然后判断差值, 最后再确定是向右向左靠拢。
如果有任何错误或疑问, 欢迎小伙伴们评论区留言^-^
( 完 )

欢迎各位看官关注

麻辣烫,走起
0%