Question
Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note:
- Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
- The solution set must not contain duplicate quadruplets.
For example, given array S = {1 0 -1 0 -2 2}, and target = 0.
A solution set is:
(-1, 0, 0, 1)
(-2, -1, 1, 2)
(-2, 0, 0, 2)
Stats
| Frequency | 2 |
| Diffficulty | 3 |
| Adjusted Difficulty | 4 |
| Time to use | ---------- |
Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)
Analysis
This is exactly the same algorithm as 3Sum. The idea is for every value pair (a, b), find all (c, d) that makes the sum equals to the target.
Note that the final found result (a, b, c, d) is already in sorted order, no need to re-sort.
Solution
The solution works in O(n^3), which is a very common solution. Read this blog for a O(n^2) solution. Read it ONLY if you are interested.
My code
public class Solution {
public List<List<Integer>> fourSum(int[] num, int target) {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
if (num == null || num.length < 4) {
return ans;
}
Arrays.sort(num);
int len = num.length;
for (int i = 0; i < len - 3; i++) {
// make sure the first number is distinct
if (i != 0 && num[i - 1] == num[i]) {
continue;
}
for (int j = i + 1; j < len - 2; j++) {
// make sure the second number is distinct
if (j != i + 1 && num[j - 1] == num[j]) {
continue;
}
int balance = target - num[i] - num[j];
int left = j + 1;
int right = len - 1;
while (left < right) {
int sum = num[left] + num[right];
if (sum == balance) {
List<Integer> lis = new ArrayList<Integer>();
lis.add(num[i]);
lis.add(num[j]);
lis.add(num[left]);
lis.add(num[right]);
ans.add(lis);
}
if (sum >= balance) {
// move right pointer left (to a unique value)
right--;
while (right >= 0 && num[right] == num[right + 1]) {
right--;
}
}
if (sum <= balance) {
// move left pointer right (to a unique value)
left++;
while (left < len && num[left] == num[left - 1]) {
left++;
}
}
}
}
}
return ans;
}
}
We can also use HashMap to remove duplication. I personally would not recommend doing this, but it gives an interesting viwepoint. Check out this code.
public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
Arrays.sort(num);
HashSet<ArrayList<Integer>> hashSet = new HashSet<ArrayList<Integer>>();
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
for (int i = 0; i < num.length; i++) {
for (int j = i + 1; j < num.length; j++) {
int k = j + 1;
int l = num.length - 1;
while (k < l) {
int sum = num[i] + num[j] + num[k] + num[l];
if (sum > target) l--;
else if (sum < target) k++;
else if (sum == target) {
ArrayList<Integer> temp =
new ArrayList<Integer>();
temp.add(num[i]);
temp.add(num[j]);
temp.add(num[k++]);
temp.add(num[l--]);
if (!hashSet.contains(temp)) {
hashSet.add(temp);
result.add(temp);
}
}
}
}
}
return result;
}