题目详情

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

给定一个整数数组，我们需要找出数组中三个元素的加和，使这个加和最接近于输入的target数值。返回这个最接近的加和。题目假设一道题只有一个答案。

For example,输入数组S = {-1 2 1 -4},目标和target = 1.

最接近target的加和是 2. (-1 + 2 + 1 = 2).

想法

• 这道题和第15题很像，所以这道题也可以选择预排序算法。
• 我们先对数组进行预排序。
• 然后通过减治思想，我们先锁定第一个元素，之后找两个元素的加和尽可能接近target和第一个元素值的差值。
• 找后两个元素的时候，使用左右指针从两端查找。

解法

public int threeSumClosest(int[] nums, int target) {        int min = Integer.MAX_VALUE;        Arrays.sort(nums);                for(int i=0;i
    
      Math.abs(diff)){                    min = diff;                    }                if(diff > 0)high--;                else low++;                                }        }                return target+min;    }