[LintCode/LeetCode] 3Sum Closest
文章目录
Problem
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.
Notice
You may assume that each input would have exactly one solution.
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).
Challenge
O(n^2) time, O(1) extra space
Note
这个题和3Sum的做法基本一样,只要在循环内计算和target最接近的和sum,并赋值更新返回值min即可。
Solution
public class Solution {
public int threeSumClosest(int[] A ,int target) {
int min = Integer.MAX_VALUE - target;
if (A.length < 3) return -1;
Arrays.sort(A);
for (int i = 0; i <= A.length-3; i++) {
int left = i+1, right = A.length-1;
while (left < right) {
int sum = A[i]+A[left]+A[right];
if (sum == target) return sum;
else if (sum < target) left++;
else right--;
min = Math.abs(min-target) < Math.abs(sum-target) ? min : sum;
}
}
return min;
}
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论