3Sum medium

Problem Statement

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: Because there are two triplets which sums to zero.

Example 2

Input: nums = [0,1,1] Output: [] Explanation: Because there is no triplet which sums to zero.

Steps

1. Sort the array: Sorting the array allows us to easily skip duplicate numbers and optimize the search for triplets.

2. Iterate through the array: We use a three-pointer approach. The outermost loop iterates through each number in the array.

3. Two-pointer approach for the remaining elements: For each number nums[i], we use two pointers, left and right, to search for pairs that sum to -nums[i]. left starts at i + 1 and right starts at the end of the array.

4. Handle duplicates: To avoid duplicate triplets, we skip duplicate numbers at each step using while loops.

5. Sum check: If the sum of nums[i], nums[left], and nums[right] equals 0, we add the triplet to the result. Then, we adjust left and right to find other possible triplets.

6. Return the result: After iterating through the entire array, we return the list of triplets.

Explanation

The core idea is to efficiently find triplets that sum to zero. Sorting allows us to use a two-pointer approach to quickly check for pairs that complement the current number to zero. The duplicate handling is crucial for ensuring the output is correct according to LeetCode's specifications. The time complexity is optimized because we avoid redundant checks due to sorting and duplicate handling.

Code

#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> result;
    sort(nums.begin(), nums.end()); // Sort the array

    for (int i = 0; i < nums.size() - 2; ++i) {
        // Skip duplicate numbers for the first element
        if (i > 0 && nums[i] == nums[i - 1]) continue;

        int left = i + 1;
        int right = nums.size() - 1;

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

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

                // Skip duplicate numbers for the second and third elements
                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 result;
}

Complexity

• Time Complexity: O(n^2), where n is the length of the input array. This is dominated by the nested loops. The sorting step takes O(n log n), but this is asymptotically smaller than O(n^2).

• Space Complexity: O(log n) in the best and average cases due to sorting (in-place sorting algorithms), and O(n) in the worst case (for example, if the array already sorted). The space used for the result vector can be considered O(n) in the worst case, as it can potentially store up to O(n) triplets. However, in most cases, the number of triplets will be much smaller than n.