三数之和

Problem

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]

Output: [[-1,-1,2],[-1,0,1]]

Explanation: nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.

nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.

nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.

The distinct triplets are [-1,0,1] and [-1,-1,2].

Notice that the order of the output and the order of the triplets does not matter.

Example 2:

Input: nums = [0,1,1]

Output: []

Explanation: The only possible triplet does not sum up to 0.

Example 3:

Input: nums = [0,0,0]

Output: [[0,0,0]]

Explanation: The only possible triplet sums up to 0.

Constraints:

• 3 <= nums.length <= 3000
• \(-10^5\) <= nums[i] <= \(10^5\)

Idea

First sort the array. Then fix the first number nums[i] and use two pointers, left starting at \(i + 1\) and right at the end, to find pairs that sum to -nums[i]: move left forward if the sum is too small, and move right backward if it is too large.

To avoid duplicate triplets, skip repeated values for the fixed number and for the left pointer after a match. Since the array is sorted, we can also stop early once nums[i] > 0.

Time complexity: \(O(n^2)\), Space complexity: \(O(\log n)\), where \(n\) is the length of nums (the space is for sorting; the output is not counted)

Pseudo Code

sort(nums);
result = empty list;
for (i = 0; i < n - 2; i++) {
    if (nums[i] > 0) {
        break;
    }
    if (i > 0 && nums[i] == nums[i - 1]) {
        continue;                          // skip duplicate first numbers
    }
    left = i + 1;
    right = n - 1;
    while (left < right) {
        sum = nums[i] + nums[left] + nums[right];
        if (sum < 0) {
            left++;
        }
        else if (sum > 0) {
            right--;
        }
        else {
            result.add([nums[i], nums[left], nums[right]]);
            left++;
            right--;
            while (left < right && nums[left] == nums[left - 1]) {
                left++;                    // skip duplicate second numbers
            }
        }
    }
}
return result;