Problem Summary

You are given an integer array nums and an integer target.
Your task is to find three integers in nums such that the sum is closest to target.
Return that sum.

You may assume there is exactly one solution.

Example
Input: nums = [-1, 2, 1, -4], target = 1
Output: 2
Explanation: The sum that is closest to 1 is 2 (from -1 + 2 + 1).

Constraints

• Array length ≥ 3
• Elements may be positive, negative, or zero
• Only one closest answer exists

---

Approach (Simple English)

This problem is a variation of the classic 3Sum two-pointer strategy.

Key observations:

1. If the array is sorted, we can fix one number and then use two pointers to search for the best sum for the remaining two numbers.
2. Sorting makes it easy to move the pointers efficiently because:
   • If the current sum is too large, move the right pointer left.
   • If the current sum is too small, move the left pointer right.
3. Track the closest sum so far using absolute difference: if |currentSum - target| < |closestSum - target|: update closestSum

Why this works
Sorting and the two-pointer method reduce the problem from O(n³) brute force to O(n²).
Since we only track closeness, we do not need to store combinations.

Detailed flow:

1. Sort the array.
2. Loop i from 0 to n-3:
   • Use two pointers:
     left = i + 1
right = n - 1
3. Compute sum = nums[i] + nums[left] + nums[right].
4. If the sum is exactly equal to target, return immediately.
5. Otherwise update the closest sum.
6. Move pointers based on comparison with target.
7. Continue until all combinations are considered.

This guarantees the closest sum is found.

---

Java Code (Optimal O(n²) Solution)

import java.util.Arrays;

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int n = nums.length;

        int closestSum = nums[0] + nums[1] + nums[2];

        for (int i = 0; i < n - 2; i++) {

            int left = i + 1;
            int right = n - 1;

            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];

                if (Math.abs(sum - target) < Math.abs(closestSum - target)) {
                    closestSum = sum;
                }

                if (sum < target) {
                    left++; 
                } else if (sum > target) {
                    right--;
                } else {
                    return sum; // exact match
                }
            }
        }
        return closestSum;
    }
}

---

Dry Run (Step-by-Step Example)

Input
nums = [-1, 2, 1, -4], target = 1

Step 1: Sort
nums = [-4, -1, 1, 2]

Initial closestSum = -4 + -1 + 1 = -4

i = 0 (nums[i] = -4)

left = 1, right = 3

1. sum = -4 + -1 + 2 = -3
   |-3 – 1| = 4 vs |-4 – 1| = 5 → update closestSum = -3
   sum < target → move left → left = 2
2. sum = -4 + 1 + 2 = -1
   |-1 – 1| = 2 vs |-3 – 1| = 4 → update closestSum = -1
   sum < target → left = 3 → stop

i = 1 (nums[i] = -1)

left = 2, right = 3

1. sum = -1 + 1 + 2 = 2
   |2 – 1| = 1 vs |-1 – 1| = 2 → update closestSum = 2
   sum > target → right = 2 → stop

i = 2 (stop loop because n – 2 = 2)

Final closestSum = 2

---

Complexity

Time complexity:
O(n²) — sorting plus two-pointer search for each element.

Space complexity:
O(1) extra space (apart from sorting).

---

Edge Cases

• Array already sorted: algorithm still works.
• All numbers positive or all negative: two-pointer logic still applies.
• Large values of integers: no overflow risk in Java int for constraints.
• Only one closest answer exists, so no tie-handling needed.