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: []
Constraints:
0 <= nums.length <= 200-109 <= nums[i] <= 109-109 <= target <= 109
Related Topics:
Array, Hash Table, Two Pointers
Similar Questions:
The brute force solution is to DFS for the 4 elements. It will take O(N^4) time. Since N^4 = 1.6e9, we will get TLE.
We can DFS for the first two elements and use two sum solution to reduce 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;
}
};