3Sum

MediumTwo Pointers

Return all unique triplets in the array that sum to zero. The solution set must not contain duplicate triplets.

Constraints

3 <= nums.length <= 3000
-10^5 <= nums[i] <= 10^5

Sort then two pointers

Time O(n^2)Space O(1) extra (excluding the output)

Sort the array. Fix each element and use two pointers on the remaining suffix to find pairs summing to its negation. Skip equal neighbours to avoid duplicate triplets.

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    int n = nums.size();
    vector<vector<int>> res;
    for (int i = 0; i < n - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        int l = i + 1, r = n - 1;
        while (l < r) {
            int sum = nums[i] + nums[l] + nums[r];
            if (sum < 0) l++;
            else if (sum > 0) r--;
            else {
                res.push_back({nums[i], nums[l], nums[r]});
                while (l < r && nums[l] == nums[l + 1]) l++;
                while (l < r && nums[r] == nums[r - 1]) r--;
                l++; r--;
            }
        }
    }
    return res;
}