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). 这道题和上一道3sum很向,只要稍微改变一下就好了
1 public class Solution { 2 public int threeSumClosest(int[] num, int target) { 3 int result = Integer.MAX_VALUE; //最后返回的结果 4 int distance = Integer.MAX_VALUE; 5 Arrays.sort(num); //对数组进行升序排序 6 boolean findTarget = false; 7 8 for(int i = 0; i < num.length; i++){ 9 int j = i + 1;10 int k = num.length - 1; //双指针11 while(j < k){12 int sum = num[i] + num[k] + num[j];13 if(target == sum){ //等于target直接返回target的值14 findTarget = true;15 result = target;16 break;17 }18 else if(sum > target){ //sum比target大k前移,同时更新result,和距离19 if(Math.abs(sum - target) < distance){20 distance = Math.abs(sum - target);21 result = sum;22 }23 k--; 24 }25 else{ //sum比target小,更新result和距离26 if(Math.abs(sum - target) < distance){27 distance = Math.abs(sum - target);28 result = sum;29 }30 j++;31 }32 }33 if(findTarget)34 break;35 }36 37 return result;38 }39 }