3 Sum Closest
31%
Accepted
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.
Have you met this question in a real interview?
Yes
Example
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).
Note
You may assume that each input would have exactly one solution.
Challenge
Tags Expand
O(n^2) time, O(1) extra space
public class Solution {
/**
* @param numbers: Give an array numbers of n integer
* @param target : An integer
* @return : return the sum of the three integers, the sum closest target.
*/
public int threeSumClosest(int[] numbers ,int target) {
// write your code here
if(numbers == null || numbers.length <= 2) return 0;
long closest = (long) Integer.MAX_VALUE;
Arrays.sort(numbers);
for(int i = 0; i < numbers.length - 2; i++){
int j = i + 1, k = numbers.length - 1;
while(j < k){
int sum = numbers[i] + numbers[j] + numbers[k];
if(numbers[i] + numbers[j] + numbers[k] == target){
return target;
} else if(numbers[i] + numbers[j] + numbers[k] > target){
k--;
} else j++;
closest = Math.abs(sum - target) > Math.abs(closest - target) ? closest : sum;
}
}
return (int) closest;
}
}
No comments:
Post a Comment