Question 16-3sum closest

解题思路

解决这道题，想法大致如下：

1. 将一整个数组排序。
2. 假定 3 个数中的其中一个，就位于数组之首，然后，通过双指针法，从数组的其他位置中找到剩下的两个，并计算这 3 个数字之和。
3. 移除数组之首，让数组之首的下一个元素成为新的数组之首，并重复第二步。

复杂度： 空间：O(n)（因为需要使用快速排序算法）时间：O(n^2)

代码

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int result = nums[0] + nums[1] + nums[nums.length - 1];
        Arrays.sort(nums);

        for (int i = 0; i < nums.length; i ++) {
            int head = i + 1;
            int tail = nums.length - 1;

            while (head < tail) {

                int curSum = nums[i] + nums[head] + nums[tail];
                if (curSum < target) {
                    head ++;
                } else if (curSum > target) {
                    tail --;
                } else {
                    return target;
                }

                if (Math.abs(target - result) > Math.abs(curSum - target)) {
                    result = curSum;
                }
            }
        }
        
        return result;
    }
}