LeetCode 16.3Sum Closest

题目

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

For example, given array S = {-1 2 1 -4}, and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

题目大意:
给定一个包含n个整数的数组和一个这个数target,从这个数组中找出三个整数使得他们的和最接近target。(Input保证存在一个正解)

分析

我们当然可以用三重循环来解决这道题,但是效率太低,并不可取。
我们先确定一个值,然后申请两个指针,再剩下的数据中找其它两个值(分别从左右两端向中间查找),这样就可以去掉一层循环。但是在查找之前要先对数组排序,这样左右两端的指针才能根据情况向中间移动

具体过程如下:
首先确定好了第一个数字后(这个用第一层循环解决),然后在剩下的数组中找两数之和,在加上第一个数字得到sum,用sum减去target 的值来跟当前的差值diff比较,如果diff比这个值大,那么更新diff 和 result。 利用two pointers (两个指针)特性,如果sum比target 小的话,说明我们需要更大的sum,所以要让left++以便得到更大的sum。如果sum 比target大的话,我们就需要更小的sum。如果相等的话,直接return就可以了。

实现代码

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
25
26
class Solution {
public int threeSumClosest(int[] nums, int target) {
int diff = Integer.MAX_VALUE;
int result = 0;
Arrays.sort(nums);
int length = nums.length;
for (int i = 0; i < length-2; i ++) {
int left = i+1;
int right = length-1;
while(left < right) {
int sum = nums[i]+nums[left]+nums[right];
if (Math.abs(target-sum) < diff) {
result = sum;
diff = Math.abs(target-sum);
}
if (sum > target)
right --;
else if(sum < target)
left ++;
else
return target;
}
}
return result;
}
}
有收获再赞赏哦🤭
------ 本文结束感谢您的阅读-------------
0%