3Sum Closest — Editorial

Opening the reading…

Intuitionwhy sorting makes the search move in one direction

Choose the first number at index i, then the other two numbers must come from the suffix after i. Once that suffix is sorted, the smallest possible pair is at the left end and the largest possible pair is at the right end. Their sum tells you which extreme can still move toward the target without skipping a better candidate.

If the three-number sum is too small, moving the right pointer left would make it even smaller, so that move cannot help. Move left inward instead. If the sum is too large, move right inward. Every visited sum is compared with the best one so far, and an exact target ends the search because no sum can be closer than zero difference.

Approachone fixed value, one monotonic pair search

Sort nums so that changing either pointer has a predictable effect on the three-number sum; without ordering, neither pointer movement would safely rule out candidates.

Initialize closest with the sum of the first three sorted values, rather than with zero or an arbitrary sentinel, so every later comparison is against a real valid triple.

For each index i from 0 through n - 3, fix nums[i] and set left to i + 1 and right to n - 1; these bounds guarantee three distinct indices while searching the remaining suffix.

Compute nums[i] + nums[left] + nums[right] and update closest when its distance from target is smaller; otherwise a nearer triple can be visited and then discarded.

If the sum is smaller than target, increment left because the sorted order makes every move of right either smaller or no better; if the sum is larger, decrement right for the symmetric reason.

If the sum equals target, return immediately because its distance from target is zero and the promised unique answer cannot be improved.

Continue while left < right, then advance i after that pair search is exhausted; every fixed index gets its own complete range without reusing an index.

Complexityquadratic scanning after one sort

MEASURE	BOUND	WHY
Time	O(n^2)	Sorting costs O(n log n). For each of the O(n) choices of i, left only moves right and right only moves left, so that inner scan performs O(n) total pointer moves rather than restarting work at every pair.
Space	O(log n) extra, worst case	The two pointers and scalar variables use O(1) space. The implementation's in-place sort may use O(log n) stack space in the worst case, so that dominates the extra bound; the returned integer requires no output storage beyond the result value.

Here n is the length of nums. The returned sum is output and is excluded from extra space.

Annotated solutionC++ · sorted array with a fixed index and two pointers

CPPSort the values, scan every fixed index, and keep the closest triple sum.

#include <algorithm>
#include <cstdlib>
#include <vector>

using namespace std;

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int closest = 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 (abs(sum - target) < abs(closest - target)) {
                    closest = sum;
                }

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

        return closest;
    }
};

The initialization of closest is deliberately tied to nums[0], nums[1], and nums[2]. Those are valid distinct indices, so the first comparison has a meaningful baseline even when every possible sum is negative or every possible sum is positive. The update uses strict inequality because an exact tie does not need to replace an already valid answer.