LeetCode016-3SumClosest

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);
        // 表示当前三数之和到target的距离，即target减去三数之和的结果的绝对值
        int distance = Integer.MAX_VALUE;
        //表示最接近target的三数之和
        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: 需要两次循环遍历
Space: 不需要使用额外的存储空间

Tips

• 解法思路与三数之和类似LeetCode015-3Sum