3Sum Closest
Question:
Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
Example1:
Given array nums = [-1, 2, 1, -4], and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
解法代碼
import java.util.Arrays;
public class LeetCode16 {
public static void main(String[] args) {
int[] nums = new int[]{-1, 2, 1, -4};
int rslt = new LeetCode16().threeSumClosest(nums, 1);
System.out.println(rslt);
}
public int threeSumClosest(int[] nums, int target) {
if(nums == null || nums.length == 0) {
throw new NullPointerException("Input array is null.");
}
Arrays.sort(nums);
// 表示當(dāng)前三數(shù)之和到target的距離巷波，即target減去三數(shù)之和的結(jié)果的絕對(duì)值
int distance = Integer.MAX_VALUE;
//表示最接近target的三數(shù)之和
int sumClosest = 0;
for(int i = 0; i < nums.length - 2; i++) {
int l = i + 1,r = nums.length - 1;
while(l < r) {
int curDistance = Math.abs(target - (nums[i] + nums[l] + nums[r]));
int curSumClosest = nums[i] + nums[l] + nums[r];
if(curSumClosest == target) {
return target;
}
if(curDistance < distance) {
distance = curDistance;
sumClosest = curSumClosest;
}
if(target < (nums[i] + nums[l] + nums[r])) {
r--;
} else {
l++;
}
}
}
return sumClosest;
}
}
Output：
2
Time And Space Complexity
Time:
需要兩次循環(huán)遍歷
Space:不需要使用額外的存儲(chǔ)空間
Tips
- 解法思路與三數(shù)之和類似LeetCode015-3Sum
