18

18. 4Sum (Medium)

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

• 0 <= a, b, c, d < n
• a, b, c, and d are distinct.
• nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

 

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 = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]

 

Constraints:

• 1 <= nums.length <= 200
• -109 <= nums[i] <= 109
• -109 <= target <= 109

Companies:
Amazon, Bloomberg, Adobe, Yahoo, Snapchat

Related Topics:
Array, Two Pointers, Sorting

Similar Questions:

• Two Sum (Easy)
• 3Sum (Medium)
• 4Sum II (Medium)

Solution 1. Two Pointers

The brute force solution is to enumerating all quadruplets. It will take O(N^4) time. Since N^4 = 1.6e9, we will get TLE.

We can enumerate the first two elements and use two pointers to get the last two elements, reducing the time complexity to O(N^3). (N^3 = 8e6)

// OJ: https://leetcode.com/problems/4sum/
// Author: github.com/lzl124631x
// Time: O(N^3)
// Space: O(1)
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& A, int target) {
        int N = A.size();
        sort(begin(A), end(A));
        vector<vector<int>> ans;
        for (int i = 0; i < N; ++i) {
            if (i > 0 && A[i] == A[i - 1]) continue;
            for (int j = i + 1; j < N; ++j) {
                if (j > i + 1 && A[j] == A[j - 1]) continue;
                int t = target - A[i] - A[j];
                for (int p = j + 1, q = N - 1; p < q; ) {
                    if (A[p] + A[q] == t) {
                        ans.push_back({ A[i], A[j], A[p++], A[q--] });
                        while (p < q && A[p] == A[p - 1]) ++p;
                        while (p < q && A[q] == A[q + 1]) --q;
                    } else if (A[p] + A[q] < t) ++p;
                    else --q;
                }
            }
        }
        return ans;
    }
};