3Closest Sum

ThreeClosestSum.java

/*
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.

    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).
    
Time Complexity : O(N^2)
*/

public int threeSumClosest(int[] A, int target) {
    int n = A.length, minDiff = Integer.MAX_VALUE, closestSum = 0;
    Arrays.sort(A);
    for ( int i = 0; i < n-2; i++ ){
        int twoSum = target - A[i];
        int j = i+1, k = n-1;
        while ( j < k ){
            int sum = A[j] + A[k];
            int diff = Math.abs(twoSum - sum);
            if (diff == 0)
                return target;
            if (diff < minDiff){
                minDiff = diff;
                closestSum = sum + A[i];
            }
            if (sum < twoSum)
                j++;
            else
                k--;
        }
    }
    return closestSum;
}