16. 3Sum Closest

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.

Example:

Given array nums = [-1, 2, 1, -4], and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

题目

找和最接近target的三个数，返回他们的和

思路

和15号问题差不多，把判断条件改一下即可

代码

public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int len =nums.length;
        int res=Integer.MAX_VALUE;//存最后的和
        int minv=Integer.MAX_VALUE;//存最小的差
        for (int i = 0; i < nums.length; i++) {
            if (i>0&&nums[i]==nums[i-1]) {
                continue;
            }
            int begin = i+1;
            int end=len-1;
            while (begin<end) {
                int sum=nums[i]+nums[begin]+nums[end];
                int minus=sum-target;
                if (minus==0) {
                    return sum;
                }else if (minus>0) {
                    if (minus<minv) {
                        minv=minus;
                        res=sum;
                    }
                    end--;
                }else {
                    if (-minus<minv) {
                        minv=-minus;
                        res=sum;
                    }
                    begin++;
                }
            }
        }
        return res;
    }