package pers.vic.basics.leetcode;

import java.util.Arrays;

/**
 * @author Vic.xu
 * @description: 16.最接近的三数之和
 * @date: 2020/11/10 8:46
 */
public class J0016_M_ThreeSumClosest {
    /*
    给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。
    返回这三个数的和。假定每组输入只存在唯一答案。
     */

    /**
     * 好像和15题的三数之和是类似的
     */
    public static int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int len = nums.length;
        int res = nums[0] + nums[1] + nums[2];
        for (int i = 0; i < len; i++) {
            int cur = nums[i];
            int l = i + 1;
            int r = len - 1;
            while (l < r) {
                int sum = cur + nums[l] + nums[r];
                //当前sum 离target更近
                if(Math.abs(target - sum) - Math.abs(target - res) < 0){
                    res = sum;
                }
                if (sum < target) {
                    l++;
                } else {
                    r--;
                }

            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {0,0,0};
        int target = 1;

        System.out.println(threeSumClosest(nums, target));
    }

}