# 16.3Sum-Closest

## ้ข็ฎๅฐๅ

https://www.lintcode.com/en/problem/3-sum-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;
}
}``````

Last updated