Leetcode 3Sum, 3Sum Closest and 4Sum
Well, these problems are very similar to Two Sum problem. You might want to check before you proceed.
Leetcode 15 3Sum
Edit 3Sum on GitHub
The problem description is as follow:
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
The solution set must not contain duplicate triplets.
For example, given array S = {-1 0 1 2 -1 -4},
A solution set is:
(-1, 0, 1)
(-1, -1, 2)
Naive Approach
As usual, brute force is always helpful, if we are not concerned about performance. We could sort the input array by ascending order and try all the possible combinations of three numbers.
public class Solution {
public List<List<Integer>> threeSum(int[] num) {
//sort array
Arrays.sort(num);
List<List<Integer>> result = new ArrayList<>();
ArrayList<Integer> each = new ArrayList<Integer>();
for(int i=0; i<num.length; i++){
if(num[i] > 0) break;
for(int j=i+1; j<num.length; j++){
if(num[i] + num[j] > 0 && num[j] > 0) break;
for(int k=j+1; k<num.length; k++){
if(num[i] + num[j] + num[k] == 0) {
each.add(num[i]);
each.add(num[j]);
each.add(num[k]);
result.add(each);
each.clear();
}
}
}
}
return result;
}
}
Since sorting will take O(nlogn) and getting all the possible combinations will take O(n^3), the overall time complexity will be O(nlogn) + O(n^3) = O(n^3)
Not-So-Naive Approach
We could set two pointers pointing at the start and end of sorted input array as the Two Sum problem. Note that in order to prevent duplicate, we use HashSet as a filter before returning the final result.
public class Solution {
public List<List<Integer>> threeSum(int[] num) {
Arrays.sort(num);
ArrayList<List<Integer>> result = new ArrayList<>();
HashSet<List<Integer>> set = new HashSet<>();
for (int i = 0; i < num.length - 2; i++) {
int start = i + 1;
int end = num.length - 1;
while (start < end) {
if (num[i] + num[start] + num[end] < 0) {
start++;
}
else if (num[i] + num[start] + num[end] > 0) {
end--;
}
else{
ArrayList<Integer> oneResult = new ArrayList<>();
oneResult.add(num[i]);
oneResult.add(num[start]);
oneResult.add(num[end]);
set.add(oneResult);
start++;
end--;
}
}
}
result.addAll(set);
return result;
}
}
The time complexity will be O(nlogn) + O(n^2) = O(n^2).
Leetcode 16 3Sum Closest
The problem description is as follow:
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
Almost the same with 3Sum problem. Since we are only returning the sum instead of combinations of numbers, it’s even simpler. We just have to make a little modification, move start and end pointer according to difference between sum and target.
public class Solution {
public int threeSumClosest(int[] num, int target) {
int closest = num[0] + num[1] + num[2];
int diff = Math.abs(closest - target);
Arrays.sort(num);
for (int i = 0; i < num.length - 2; i++) {
int start = i + 1;
int end = num.length - 1;
while (start < end) {
int sum = num[i] + num[start] + num[end];
int newDiff = Math.abs(sum - target);
if (newDiff == 0) {
return target;
}
if (newDiff < diff) {
diff = newDiff;
closest = sum;
}
if (sum < target)
start++;
else
end--;
}
}
return closest;
}
}
The time complexity will still be O(nlogn) + O(n^2) = O(n^2).
Leetcode 18 4Sum
The problem description is as follow:
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)
This problem is exactly the same as 3Sum:
public class Solution {
public List<List<Integer>> fourSum(int[] num, int target) {
HashSet<ArrayList<Integer>> hashSet = new HashSet<ArrayList<Integer>>();
List<List<Integer>> result = new ArrayList<>();
if(num.length < 4) {
return result;
}
Arrays.sort(num);
for (int i = 0; i < num.length - 3; i++) {
for (int j = i + 1; j < num.length - 2; 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]);
hashSet.add(temp);
k++;
l--;
}
}
}
}
result.addAll(hashSet);
return result;
}
}
The time complexity is O(nlogn) + O(n^3) = O(n^3).
