首页 > 代码库 > 3Sum Closest leetcode java
3Sum Closest leetcode java
题目:
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).
题解:
这道题也是3sum的变体,这里找到的不仅使3sum==target,同时如果没有找到==target的3sum要返回最接近target的值。
于是,这就需要在使用二分查找法时遍历数组的时候,维护一个最接近target值min,这样当完全遍历完数组扔没找到与target相等的3sum时,可以返回维护的这个min值。
这道题比3sum和4sum简单的地方就是不需要判断重复问题,因为题目给我们减轻了去重的压力,have exactly one solution。
即便要求去重,使用之前说过的两个方法:HashSet和挪动指针法,也可以很容易就去重了。
这里要注意,判断closest的方法是采取target-sum的绝对值与min相比,很容易理解,无论这个closest是在target左还是右,离target最近的就是最closest的。
实现代码如下:
1 public int threeSumClosest(int[] num, int target) {
2 if(num==null || num.length<3)
3 return 0;
4
5 int min = Integer.MAX_VALUE;
6 int val = 0;
7 Arrays.sort(num);
8 for(int i = 0; i<=num.length-3;i++){
9 int low = i+1;
10 int high = num.length-1;
11 while(low<high){
12 int sum = num[i]+num[low]+num[high];
13 if(Math.abs(target-sum)<min){
14 min = Math.abs(target-sum);
15 val = sum;
16 }
17
18 if(target==sum){
19 return val;
20 }else if(target>sum){
21 low++;
22 }else{
23 high--;
24 }
25 }
26 }
27 return val;
28 }
2 if(num==null || num.length<3)
3 return 0;
4
5 int min = Integer.MAX_VALUE;
6 int val = 0;
7 Arrays.sort(num);
8 for(int i = 0; i<=num.length-3;i++){
9 int low = i+1;
10 int high = num.length-1;
11 while(low<high){
12 int sum = num[i]+num[low]+num[high];
13 if(Math.abs(target-sum)<min){
14 min = Math.abs(target-sum);
15 val = sum;
16 }
17
18 if(target==sum){
19 return val;
20 }else if(target>sum){
21 low++;
22 }else{
23 high--;
24 }
25 }
26 }
27 return val;
28 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。