28. 4Sum

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Notice that the solution set must not contain duplicate quadruplets.

Example 1:

Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Example 2:

Input: nums = [], target = 0
Output: []

Solution: (Using Sorting and 3SUM)

class Solution
{
public:
    vector<vector<int>> fourSum(vector<int> &nums, int target)
    {

        sort(nums.begin(), nums.end());
        vector<vector<int>> res;

        int i = 0;
        while (i < nums.size())
        {
            int a1 = nums[i];

            int j = i + 1;
            while (j < nums.size())
            {
                int a2 = nums[j];

                int t = a1 + a2;

                int start = j + 1;
                int end = nums.size() - 1;

                while (start < end)
                {

                    if (nums[start] + nums[end] + t == target)
                    {
                        int t1 = nums[start];
                        int t2 = nums[end];
                        vector<int> v;
                        v.push_back(a1);
                        v.push_back(a2);
                        v.push_back(nums[start]);
                        v.push_back(nums[end]);
                        res.push_back(v);

                        while (start < nums.size() && nums[start] == t1)
                        {
                            start++;
                        }

                        while (end >= 0 && nums[end] == t2)
                        {
                            end--;
                        }
                    }
                    else if (nums[start] + nums[end] + t > target)
                    {
                        end--;
                    }
                    else
                    {
                        start++;
                    }
                }

                while (j < nums.size() && nums[j] == a2)
                {
                    j++;
                }
            }

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

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

4Sum II

Given four integer arrays nums1, nums2, nums3, and nums4 all of length n, return the number of tuples (i, j, k, l) such that:

• 0 <= i, j, k, l < n

• nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

Example 1:

Input: nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
Output: 2
Explanation:
The two tuples are:
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

Example 2:

Input: nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
Output: 1

Solution: (2 Sum)

class Solution
{
public:
    int fourSumCount(vector<int> &nums1, vector<int> &nums2, vector<int> &nums3, vector<int> &nums4)
    {
        unordered_map<int, int> m;
        int res = 0;
        
        for (int i = 0; i < nums1.size(); i++)
        {
            for (int j = 0; j < nums2.size(); j++)
            {
                int s = nums1[i] + nums2[j];
                m[s]++;
            }
        }

        for (int i = 0; i < nums3.size(); i++)
        {
            for (int j = 0; j < nums4.size(); j++)
            {
                int s = nums3[i] + nums4[j];
                if (m.find(-s) != m.end())
                {
                    res += m[-s];
                }
            }
        }

        return res;
    }
};

Time Complexity: O(n^2)