16 3Sum Closest

Leetcode

Given an integer array nums of length n 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.

Example 1:

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Example 2:

Input: nums = [0,0,0], target = 1
Output: 0

---

和 3 sum 类似，排序后固定一个点，另外两个指针移动。如果当前的和和 target 相差最小，更新最小记录。如果相差 0 ，说明已经命中，可以直接返回。

public int threeSumClosest(int[] nums, int target) {
    Arrays.sort(nums);
    int left,right;
    int min=Integer.MAX_VALUE;
    int res=0;
    for(int i=0;i<nums.length-2;++i){
        left=i+1;
        right=nums.length-1;
        int remain=target-nums[i];
        while(left<right){
            int sum=nums[left]+nums[right];
            if(sum>remain){
                if(sum-remain<min) {
                    min=sum-remain;
                    res=sum+nums[i];
                }
                right--;
            } else if(sum<remain){
                if(remain-sum<min) {
                    min=remain-sum;
                    res=sum+nums[i];
                }
                left++;
            } else {
                return sum+nums[i];
            }
        }
    }
    return res;
}