Return the sum of three integers whose total is closest to a target value. Test your code, then compare with the explained solution. Free online practice.

3Sum Closest

Combination Sum II

Binary Tree Inorder Traversal

Return the sum of three integers whose total is closest to a target value.

Given an integer array `nums` of length at least 3 and an integer `target`, choose three distinct indices `i`, `j`, and `k` and return the sum `nums[i] + nums[j] + nums[k]` whose value is closest to `target`.

You only need to return the closest **sum**, not the actual triplet.

**Input / output**
- Input: `nums: int[]`, `target: int`
- Output: `int`

**Examples**
1. `nums = [-1, 2, 1, -4]`, `target = 1` returns `2` because `(-1 + 2 + 1) = 2`, which is closest to `1`.
2. `nums = [0, 0, 0]`, `target = 1` returns `0`.
3. `nums = [1, 2, 4]`, `target = 8` returns `7` because that is the only possible triplet sum.

**Constraints**
- `3 <= nums.length <= 500`
- `-1000 <= nums[i] <= 1000`
- `-10^4 <= target <= 10^4`
- Exactly one sum is closest to `target` in the test data, so no tie-breaking rule is needed between two different sums.

**Follow-up**
Can you improve the brute-force `O(n^3)` search by sorting the array first and then using a two-pointer scan for each fixed first value?

- Any valid answer comes from choosing three different indices.
- The most direct solution is to try every triplet, compute its sum, and keep the one with the smallest absolute distance from `target`.
- This is easy to reason about and makes a good correctness baseline, but it checks `O(n^3)` triplets.

Start with the brute-force search space

- Initialize `best_sum` using the first three values.
- Enumerate every `i < j < k` combination, compute the current sum, and update `best_sum` whenever the new sum is closer to `target`.
- Because the problem guarantees exactly one closest sum, a strict `<` comparison is enough when updating the best answer.

Brute-force triple loop

- After sorting, fix one value `nums[i]` and search for the best pair in the suffix `i + 1 .. n - 1`.
- With a sorted array, if the current triplet sum is too small, moving `left` right is the only way to increase it; if the sum is too large, moving `right` left decreases it.
- This turns the inner `O(n^2)` pair search into a linear two-pointer walk for each fixed `i`, reducing the total to `O(n^2)` after sorting.

Sort first, then scan with two pointers

Sort the array, initialize the best answer from the first triplet, then for each index run a two-pointer scan to keep improving the closest sum. Sorting costs `O(n log n)`, the scans cost `O(n^2)`, and the total is `O(n^2)` with `O(1)` extra space beyond the sort.