3Sum Closest

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.

Example

For example, given array S = [-1 2 1 -4], and target = 1. The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Notes:

1. Fixed one point and use two pointers
2. Don't forget to sort the array
3. time: O(n^2)

    public int threeSumClosest(int[] nums, int target) {
        if (nums == null || nums.length < 3) {
            return 0;
        }

        Arrays.sort(nums);

        int sum = nums[0] + nums[1] + nums[2];
        for (int i = 0; i < nums.length; ++i) {
            int j = i+1;
            int k = nums.length-1;
            while(j < k) {
                int temp = nums[i] + nums[j] + nums[k];
                if (Math.abs(temp-target) < Math.abs(sum - target)) {
                    sum = temp;
                }

                if (temp < target) {
                    j++;
                } else if (temp > target) {
                    k--;
                } else {
                    return sum;
                }
            }
        }

        return sum;
    }