Comment on page

16.3Sum-Closest

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).

代码

Approach #1

public class Solution {
public int threeSumClosest(int[] nums, int target) {
if (num.length <= 3) {
int sum = 0;
for (int num : nums) {
sum += num;
}
return sum;
}
// 1. sort
Arrays.sort(nums);
int n = nums.length;
int result = nums[0] + nums[1] + nums[2];
// 2. for-loop
for (int i = 0; i < n - 2; ++i) {
// 3. two points
int start = i + 1;
int end = n - 1;
while (start < end) {
int temp = nums[i] + nums[start] + nums[end];
if (abs(target - temp) < abs(target - result)) {
result = temp;
}
if (result == target) return result;
if (temp > target) {
--end;
} else {
++start;
}
}
}
return result;
}
}