27. 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.

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]]


Example 2:
Input: nums = []
Output: []


Example 3:
Input: nums = [0]
Output: []

Solution: (Bruteforce)

Using hash map and set

class Solution
{
public:
    vector<vector<int>> threeSum(vector<int> &nums)
    {

        vector<vector<int>> res;

        unordered_map<int, int> m;
        set<vector<int>> s;

        for (int i = 0; i < nums.size(); i++)
        {
            m[nums[i]]++;
        }

        for (int i = 0; i < nums.size(); i++)
        {
            m[nums[i]]--;
            for (int j = i + 1; j < nums.size(); j++)
            {
                m[nums[j]]--;
                int x = nums[i] + nums[j];

                if (m.find(-x) != m.end())
                {
                    if (m[-x] > 0)
                    {
                        vector<int> v;
                        v.push_back(nums[i]);
                        v.push_back(nums[j]);
                        v.push_back(-x);
                        sort(v.begin(), v.end());
                        s.insert(v);
                    }
                }
                m[nums[j]]++;
            }
            m[nums[i]]++;
        }

        for (auto itr = s.begin(); itr != s.end(); itr++)
        {
            vector<int> k = *itr;
            res.push_back(k);
        }
        return res;
    }
};

Time Complexity: O(n^2 + log m)

Solution: (Using Sorting and 2Sum)

class Solution
{
public:
    vector<vector<int>> threeSum(vector<int> &nums)
    {

        int n = nums.size();

        vector<vector<int>> res;
        if (n < 3)
        {
            return res;
        }

        sort(nums.begin(), nums.end());

        int i = 0;
        while (i < nums.size())
        {
            int prev = nums[i];
            int target = -prev;

            int low = i + 1;
            int high = n - 1;

            while (low < high)
            {
                if (nums[low] + nums[high] == target)
                {

                    res.push_back({prev, nums[low], nums[high]});

                    int prevLow = low;
                    int prevHigh = high;

                    while (low < n && nums[low] == nums[prevLow])
                    {
                        low++;
                    }
                    while (high >= i + 1 && nums[high] == nums[prevHigh])
                    {
                        high--;
                    }
                }
                else if (nums[low] + nums[high] < target)
                {
                    low++;
                }
                else
                {
                    high--;
                }
            }

            while (i < nums.size() && nums[i] == prev)
            {
                i++;
            }
        }

        return res;
    }
};

Time Complexity: O(n log n + n^2)