16. 3Sum Closest

Sort the array, then fix each element and sweep the remaining range with two pointers. Because the array is sorted, moving the pointer inward changes the sum predictably: if the current triple is below target move the left pointer right, otherwise move the right pointer left. Track the closest sum seen.

Sort, then fix-and-sweep

Sort nums. Fix the first element at index i, then use two pointers l = i+1 and r = n-1 to explore all pairs to its right in O(n).

Why the pointers move deterministically

With the array sorted, for a fixed i the sum nums[i] + nums[l] + nums[r]:

• if it is less than target, the only way to grow it is to move l right (to a larger value);
• if it is greater than target, move r left (to a smaller value);
• if it equals target, it's the best possible — return immediately.

Along the way keep best = the sum whose distance |sum - target| is smallest.

best = nums[0]+nums[1]+nums[2]
for i in 0..n-3:
    l, r = i+1, n-1
    while l < r:
        s = nums[i]+nums[l]+nums[r]
        if |s-target| < |best-target|: best = s
        if s < target: l += 1
        elif s > target: r -= 1
        else: return s
return best

Worked example

nums = [-1, 2, 1, -4], target = 1 → sorted [-4, -1, 1, 2].

• i=0 (-4): l=1,r=3 → -4-1+2 = -3 (dist 4); -3<1 move l. l=2: -4+1+2 = -1 (dist 2, best=-1); -1<1 move l. l=r stop.
• i=1 (-1): l=2,r=3 → -1+1+2 = 2 (dist 1, best=2); 2>1 move r. stop.

Closest sum = 2.

Complexity

• Time: O(n^2) — one two-pointer sweep per fixed element.
• Space: O(1) beyond sorting.

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int n = nums.length;
        int best = nums[0] + nums[1] + nums[2];
        for (int i = 0; i < n - 2; i++) {
            int l = i + 1, r = n - 1;
            while (l < r) {
                int s = nums[i] + nums[l] + nums[r];
                if (Math.abs(s - target) < Math.abs(best - target)) best = s;
                if (s < target) l++;
                else if (s > target) r--;
                else return s;
            }
        }
        return best;
    }
}