LeetCode 16. 3Sum Closest(最接近的三数

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

示例:

给定数组 nums = [-1，2，1，-4], 和 target = 1.
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

思路:

• 比15题更加简单,确定一个数,然后用头尾双指针确定另两个数即可
• 先使用Arrays.sort()方法进行排序,使头尾指针有意义

代码:

    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int res  = Integer.MAX_VALUE,res1 = 0,add,temp,flag= Integer.MAX_VALUE;
        for (int k = 0; k < nums.length; k++) {
            int i = k + 1, j = nums.length - 1;
            while (i < j) {
                temp = nums[k] +nums[i] + nums[j];
                add = target -temp;
                flag = Math.abs(add);
                if (flag < res) {
                    res = flag;
                    res1 = temp;
                } 
                if (add > 0)
                    i++;
                else
                    j--;
            }
        }
        return res1;  
    }

总结:

• 数组题都较为考验对循环的掌握能力,用最小的代价获取最关键的信息
• 使用头尾双指针需要注意没有漏过一些答案组合
• 在没有思路时,使用Arrays.sort()进行排序,能提供新的可行道路