# 15. 3Sum

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

# Solution

Approach 1: Sorting and then for each number, do 2-sum for the rest of numbers. (Deduplication is tricky.)

Approach 2: use a hashtable to record numbers/pairs seen, deduplicate using a set.

# Code (Python)

Approach 1:

    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result = []
        
        # fixing the highest index wouldn't work for cases like [-2,0,1,1,2] since 1 == 1 and got skipped, it'll miss the solution (-1,1,1)
        [-2,-2,0,1,1,2]
        
        for low in range(len(nums) - 2):
            if low > 0 and nums[low] == nums[low-1]:
                continue
            
            l, r = low + 1, len(nums) - 1
            while l < r:
                if nums[low] + nums[l] + nums[r] < 0:
                    l += 1
                elif nums[low] + nums[l] + nums[r] > 0:
                    r -= 1
                else:
                    result.append((nums[low], nums[l], nums[r]))
                    l += 1
                    # note l < r to prevent index out of bound
                    while l < r and nums[l] == nums[l-1]:
                        l += 1
                    r -= 1
                    while l < r and nums[r] == nums[r+1]:
                        r -= 1
            
        return result

Approach 2 (Time Limit Exceeded):

    def threeSum(self, nums: List[int]) -> List[List[int]]:
        table = defaultdict(list)
        result = set()
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                table[nums[i] + nums[j]].append((i, j))
        for k in range(len(nums)):
            for pair in table[-nums[k]]:
                if k != pair[0] and k != pair[1]:
                    result.add(tuple(sorted([nums[k], nums[pair[0]], nums[pair[1]]])))
        return list(result)

# Code (C++)

Approach 1:

class Solution {
private:
/*
    // Hash table.
    vector<vector<int>> twoSum(vector<int>& nums, int head, int tail, int target) {
        vector<vector<int>> res;
        unordered_set<int> visited;
        for (int i = head; i <= tail; ++i)
        {
            if (i >= head + 2 && nums[i] == nums[i-1] && nums[i-1] == nums[i-2]) // e.g., [-2,0,1,1,2].
                continue;
            int tmp = target - nums[i];
            if (visited.find(tmp) != visited.end())
            {
                vector<int> pair = vector<int>();
                pair.push_back(nums[i]);
                pair.push_back(tmp);
                res.push_back(pair);
                visited.erase(tmp); // e.g., [-2,0,0,2,2].
            }
            else
                visited.insert(nums[i]);
        }
        return res;
    }
*/
    // Two pointers.
    vector<vector<int>> twoSum(vector<int>& nums, int head, int tail, int target) {
        vector<vector<int>> res;
        int i = head;
        int j = tail;
        while (i < j)
        {
            if (i > head && nums[i] == nums[i-1])
                i++;
            else if (j < nums.size() - 1 && nums[j] == nums[j+1])
                j--;
            else
            {
                int sum = nums[i] + nums[j];
                if (sum < target)
                    i++;
                else if (sum > target)
                    j--;
                else
                {
                    vector<int> pair = vector<int>();
                    pair.push_back(nums[i]);
                    pair.push_back(nums[j]);
                    res.push_back(pair);
                    i++;
                    j--;
                }
            }
        }
        return res;
    }

public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        std::sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); ++i)
        {
            if (i > 0 && nums[i] == nums[i-1])
                continue;
            vector<vector<int>> pairs =
                twoSum(nums, i + 1, nums.size() - 1, 0 - nums[i]);
            for (auto it = pairs.begin(); it != pairs.end(); ++it)
            {
                it->push_back(nums[i]);
                res.push_back(*it);
            }
        }
        return res;
    }
};