3Sum

Problem Statement

In the given problem, we need to identify all unique triplets within an integer array nums that can sum up to zero. The triplets must be formed such that no index is used more than once within a single triplet, meaning for a triplet [nums[i], nums[j], nums[k]], it must hold that i != j, i != k, and j != k. Additionally, it's crucial to ensure that the resulting list of triplets does not include any duplicates. This scenario requires an efficient approach to both generate potential triplets and to check if their sum equals zero, while also maintaining uniqueness amongst the results in terms of the values and not just the indices.

Examples

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
• -105 <= nums[i] <= 105

Approach and Intuition

The solution to this problem revolves around avoiding unnecessary computations and ensuring that we do not revisit the same elements in such a way that would produce duplicate triplets. Here's a step-by-step breakdown:

1. First, sort the array. This will make it easier to skip duplicates and use the two-pointer technique efficiently.
2. Iterate through the sorted array using a loop. Let the current element at index i be the first element of the triplet.
3. Within this loop, initiate two pointers: one (left) at i+1 and the other (right) at the end of the array. This will facilitate checking pairs in a range that decreases as i increases, avoiding recomputation and duplicates naturally.
4. For each position of i, move the left and right pointers based on the sum:
   • If nums[i] + nums[left] + nums[right] == 0, record the triplet and shift both pointers to skip any duplicates around them.
   • If the sum is less than zero, move the left pointer to the right to increase the sum.
   • If the sum is greater than zero, move the right pointer to the left to decrease the sum.
5. A significant part of avoiding duplicates involves, after finding a valid triplet, skipping all other i values which are the same as nums[i]. This is done by incrementing i as long as nums[i] is the same as the number at the next index.

This method ensures that each potential triplet is checked minimally and efficiently, leveraging sorting and the two-pointer technique, which are particularly powerful for such array transformation problems given their ability to significantly cut down the number of required operations. Moreover, the array being sorted helps prevent the formation of duplicate triplets and allows for easy skipping of repeated values, which optimizes the overall process.

Solutions

class Solution {
public:
    vector<vector<int>> findThreeSum(vector<int>& nums) {
        set<vector<int>> resultSet;
        unordered_set<int> duplicateSet;
        unordered_map<int, int> indexMap;
        for (int i = 0; i < nums.size(); ++i)
            if (duplicateSet.insert(nums[i]).second) {
                for (int j = i + 1; j < nums.size(); ++j) {
                    int needed = -nums[i] - nums[j];
                    auto it = indexMap.find(needed);
                    if (it != indexMap.end() && it->second == i) {
                        vector<int> triple = {nums[i], nums[j], needed};
                        sort(triple.begin(), triple.end());
                        resultSet.insert(triple);
                    }
                    indexMap[nums[j]] = i;
                }
            }
        return vector<vector<int>>(resultSet.begin(), resultSet.end());
    }
};