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 – Solve Online

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.