3Sum

Intuitionwhy sorting makes duplicate-free search possible

A triplet is determined by choosing its smallest, middle, and largest values after sorting. Fix the first value at index i, then search for two later values whose sum is -nums[i]. Because the remaining values are sorted, the two-pointer positions describe a complete search interval rather than an arbitrary collection of pairs.

If the current three-value sum is too small, moving the left pointer right is the only useful move: every value before it is no larger and would keep the sum too small. If the sum is too large, moving the right pointer left is the only useful move. When the sum is zero, record it and skip equal values so the same value triplet cannot return through different indices.

Approachone fixed value, one monotone pair search

1. 1Sort nums so increasing a value always increases the three-value sum and decreasing a value always decreases it; without this order, neither pointer move would safely discard candidates.
2. 2Loop i from 0 through n - 3 and treat nums[i] as the first value; stopping at n - 3 leaves two positions for the other values.
3. 3Skip i when nums[i] equals nums[i - 1], because fixing the same first value again would search the same value combinations and create duplicate triplets.
4. 4Set left to i + 1 and right to n - 1, because every pair that completes the fixed value lies inside this still-unsearched interval.
5. 5Compute nums[i] + nums[left] + nums[right]. Move left rightward when the sum is negative and right leftward when it is positive, because sorted order proves that the opposite move cannot reach zero.
6. 6When the sum is zero, append the three values, skip all equal values at both pointers, and then move both pointers inward; this records the value combination once and prevents its repeated indices from producing duplicates.
7. 7Return the result after every fixed position has been processed, because the outer loop covers every possible first value and the inner search covers every viable pair for that value.

Complexitysorting plus a linear scan for each fixed position

Annotated solutionC++ · sorted two pointers · complete judge-ready implementation

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());
        int n = nums.size();

        for (int i = 0; i < n - 2; ++i) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;

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

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

                if (sum == 0) {
                    res.push_back({nums[i], nums[left], nums[right]});

                    while (left < right && nums[left] == nums[left + 1]) {
                        ++left;
                    }
                    while (left < right && nums[right] == nums[right - 1]) {
                        --right;
                    }
                    ++left;
                    --right;
                } else if (sum < 0) {
                    ++left;
                } else {
                    --right;
                }
            }
        }

        return res;
    }
};

The two duplicate checks happen at different levels. The check on i prevents repeating an entire search for the same first value. The checks after a match prevent repeating the same second or third value within that search. The final left and right increments are still necessary after skipping duplicates, because otherwise the loop would remain on the values that just produced the recorded triplet.

The hash-set alternativea reasonable different arrangement, with more working memory

You can keep the sort and replace the inward pair scan with a set for each fixed i. Walk j from i + 1 to the end and ask whether the needed third value, -nums[i] - nums[j], has already appeared in this scan. Since the array is sorted, skipping repeated j values is enough to avoid duplicate triplets for the fixed i.

#include <algorithm>
#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());
        int n = nums.size();

        for (int i = 0; i < n - 2; ++i) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            unordered_set<int> seen;
            for (int j = i + 1; j < n; ++j) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;

                int needed = -nums[i] - nums[j];
                if (seen.count(needed)) {
                    res.push_back({nums[i], needed, nums[j]});
                }
                seen.insert(nums[j]);
            }
        }

        return res;
    }
};

This is a different arrangement, not an asymptotic improvement. It still takes O(n^2) average time after sorting, but each fixed value creates a set that can hold O(n) values, so the extra space becomes O(n) rather than the two-pointer state's O(1). The two-pointer solution is usually preferable because it avoids hashing and gives a deterministic movement proof.

Common mistakesthe duplicate and pointer rules that change the answer