Leecode no.16 最接近的三数之和

package com.example.demo.leecode;

/**
 * 最接近的三数之和
 * @Date 2020/12/2
 * @author Tang
 *
 * 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。
 * 找出 nums 中的三个整数，使得它们的和与 target 最接近。
 * 返回这三个数的和。假定每组输入只存在唯一答案。
 */
public class ThreeSumClosest {


    /**
     * 整体思路：
     * 先给数组排序
     * 遍历数组 每个元素nums[i] 存一个临时结果temp
     * 利用两个指针  头指针nums[i-1]  尾指针nums[lenth-1] 三个数相加与target比较大小
     * 如果大小相同直接返回  如果大于target 头指针后移    如果小于target 尾指针前移  直到两个指针碰撞
     * 还需要比较target-temp距离  与当前的距离比较，如果距离更小更新temp
     *
     * 效果：和穷举相比,通过有序数组 减少了一些不必要的相加比较
     * @param nums
     * @param target
     * @return
     */
    public int execute(int[] nums, int target){
        if(nums.length < 3){
            return 0;
        }
        //先排序
        nums = quiceSort(nums, 0, nums.length - 1);

        int temp = nums[0] + nums[1] + nums[2];
        for(int i = 0; i < nums.length; i++){
            int head = i+1;
            int tail = nums.length - 1;
            while(head < tail){
                int count = nums[i] + nums[head] + nums[tail];

                temp = Math.abs(target - count) < Math.abs(target - temp) ? count : temp;

                if(count > target){
                    tail--;
                }else if(count < target){
                    head++;
                }else{
                    return temp;
                }
            }

        }
        return temp;
    }

    /**
     * 快排
     * @return
     */
    private int[] quiceSort(int nums[], int begin, int end){
        if(begin >= end){
            return nums;
        }
        int i = begin;
        int j = end;
        int base = nums[begin];

        while(i < j){

            while(nums[j] > base){
                j--;
            }

            if(i < j){
                int temp = nums[j];
                nums[j] = nums[i];
                nums[i] = temp;
                i++;
            }

            while(nums[i] < base){
                i++;
            }

            if(i < j){
                int temp = nums[j];
                nums[j] = nums[i];
                nums[i] = temp;
                j--;
            }

        }
        nums[i] = base;
        int[] leftNums = quiceSort(nums, begin, i - 1);
        int[] rightNums = quiceSort(leftNums, i + 1, end);

        return rightNums;
    }

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

        ThreeSumClosest sumClosest = new ThreeSumClosest();
        System.out.println(sumClosest.execute(array,100));


    }
}