3 Sum

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:
given array S = {-1 2 1 -4},
and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2)

Method:

see solution

Solution:

Time: O(nlogn)
Space: O(1)

public class Solution {
    public int threeSumClosest(ArrayList<Integer> A, int B) {
        Collections.sort(A);
        int closest = A.get(0) + A.get(1) + A.get(2);
        for (int i = 0; i < A.size() - 2; i ++) {
            int iVal = A.get(i);
            int j = i + 1;
            int k = A.size() - 1;
            while (j < k) {
                int jVal = A.get(j);
                int kVal = A.get(k);
                int candidate = iVal + jVal + kVal;
                if (Math.abs(candidate - B) < Math.abs(closest - B)) {
                    closest = candidate;
                    j ++;
                } else if (candidate > B) {
                    k --;
                } else {
                    j ++;
                }
            }
        }
        return closest;
    }
}