Table of Contents
4Sum – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
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 < na,b,c, anddare 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
C++ 4Sum LeetCode Solution
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> total;
int n = nums.size();
if(n<4) return total;
sort(nums.begin(),nums.end());
for(int i=0;i<n-3;i++)
{
if(i>0&&nums[i]==nums[i-1]) continue;
if(nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target) break;
if(nums[i]+nums[n-3]+nums[n-2]+nums[n-1]<target) continue;
for(int j=i+1;j<n-2;j++)
{
if(j>i+1&&nums[j]==nums[j-1]) continue;
if(nums[i]+nums[j]+nums[j+1]+nums[j+2]>target) break;
if(nums[i]+nums[j]+nums[n-2]+nums[n-1]<target) continue;
int left=j+1,right=n-1;
while(left<right){
int sum=nums[left]+nums[right]+nums[i]+nums[j];
if(sum<target) left++;
else if(sum>target) right--;
else{
total.push_back(vector<int>{nums[i],nums[j],nums[left],nums[right]});
do{left++;}while(nums[left]==nums[left-1]&&left<right);
do{right--;}while(nums[right]==nums[right+1]&&left<right);
}
}
}
}
return total;
}
};
Java 4Sum LeetCode Solution
public class Solution {
int len = 0;
public List<List<Integer>> fourSum(int[] nums, int target) {
len = nums.length;
Arrays.sort(nums);
return kSum(nums, target, 4, 0);
}
private ArrayList<List<Integer>> kSum(int[] nums, int target, int k, int index) {
ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();
if(index >= len) {
return res;
}
if(k == 2) {
int i = index, j = len - 1;
while(i < j) {
//find a pair
if(target - nums[i] == nums[j]) {
List<Integer> temp = new ArrayList<>();
temp.add(nums[i]);
temp.add(target-nums[i]);
res.add(temp);
//skip duplication
while(i<j && nums[i]==nums[i+1]) i++;
while(i<j && nums[j-1]==nums[j]) j--;
i++;
j--;
//move left bound
} else if (target - nums[i] > nums[j]) {
i++;
//move right bound
} else {
j--;
}
}
} else{
for (int i = index; i < len - k + 1; i++) {
//use current number to reduce ksum into k-1sum
ArrayList<List<Integer>> temp = kSum(nums, target - nums[i], k-1, i+1);
if(temp != null){
//add previous results
for (List<Integer> t : temp) {
t.add(0, nums[i]);
}
res.addAll(temp);
}
while (i < len-1 && nums[i] == nums[i+1]) {
//skip duplicated numbers
i++;
}
}
}
return res;
}
}
Python 3 4Sum LeetCode Solution
def fourSum(self, nums, target):
nums.sort()
results = []
self.findNsum(nums, target, 4, [], results)
return results
def findNsum(self, nums, target, N, result, results):
if len(nums) < N or N < 2: return
# solve 2-sum
if N == 2:
l,r = 0,len(nums)-1
while l < r:
if nums[l] + nums[r] == target:
results.append(result + [nums[l], nums[r]])
l += 1
r -= 1
while l < r and nums[l] == nums[l - 1]:
l += 1
while r > l and nums[r] == nums[r + 1]:
r -= 1
elif nums[l] + nums[r] < target:
l += 1
else:
r -= 1
else:
for i in range(0, len(nums)-N+1): # careful about range
if target < nums[i]*N or target > nums[-1]*N: # take advantages of sorted list
break
if i == 0 or i > 0 and nums[i-1] != nums[i]: # recursively reduce N
self.findNsum(nums[i+1:], target-nums[i], N-1, result+[nums[i]], results)
return
def fourSum(self, nums, target):
def findNsum(nums, target, N, result, results):
if len(nums) < N or N < 2 or target < nums[0]*N or target > nums[-1]*N: # early termination
return
if N == 2: # two pointers solve sorted 2-sum problem
l,r = 0,len(nums)-1
while l < r:
s = nums[l] + nums[r]
if s == target:
results.append(result + [nums[l], nums[r]])
l += 1
while l < r and nums[l] == nums[l-1]:
l += 1
elif s < target:
l += 1
else:
r -= 1
else: # recursively reduce N
for i in range(len(nums)-N+1):
if i == 0 or (i > 0 and nums[i-1] != nums[i]):
findNsum(nums[i+1:], target-nums[i], N-1, result+[nums[i]], results)
results = []
findNsum(sorted(nums), target, 4, [], results)
return results
def fourSum(self, nums, target):
def findNsum(l, r, target, N, result, results):
if r-l+1 < N or N < 2 or target < nums[l]*N or target > nums[r]*N: # early termination
return
if N == 2: # two pointers solve sorted 2-sum problem
while l < r:
s = nums[l] + nums[r]
if s == target:
results.append(result + [nums[l], nums[r]])
l += 1
while l < r and nums[l] == nums[l-1]:
l += 1
elif s < target:
l += 1
else:
r -= 1
else: # recursively reduce N
for i in range(l, r+1):
if i == l or (i > l and nums[i-1] != nums[i]):
findNsum(i+1, r, target-nums[i], N-1, result+[nums[i]], results)
nums.sort()
results = []
findNsum(0, len(nums)-1, target, 4, [], results)
return results
Array-1180
String-562
Hash Table-412
Dynamic Programming-390
Math-368
Sorting-264
Greedy-257
Depth-First Search-256
Database-215
Breadth-First Search-200
Tree-195
Binary Search-191
Matrix-176
Binary Tree-160
Two Pointers-151
Bit Manipulation-140
Stack-133
Heap (Priority Queue)-117
Design-116
Graph-108
Simulation-103
Prefix Sum-96
Backtracking-92
Counting-86
Sliding Window-73
Linked List-69
Union Find-66
Ordered Set-48
Monotonic Stack-47
Recursion-43
Trie-41
Binary Search Tree-40
Divide and Conquer-40
Enumeration-39
Bitmask-37
Queue-33
Memoization-32
Topological Sort-31
Geometry-30
Segment Tree-27
Game Theory-24
Hash Function-24
Binary Indexed Tree-21
Interactive-18
Data Stream-17
String Matching-17
Rolling Hash-17
Shortest Path-16
Number Theory-16
Combinatorics-15
Randomized-12
Monotonic Queue-9
Iterator-9
Merge Sort-9
Concurrency-9
Doubly-Linked List-8
Brainteaser-8
Probability and Statistics-7
Quickselect-7
Bucket Sort-6
Suffix Array-6
Minimum Spanning Tree-5
Counting Sort-5
Shell-4
Line Sweep-4
Reservoir Sampling-4
Eulerian Circuit-3
Radix Sort-3
Strongly Connected Componen-t2
Rejection Sampling-2
Biconnected Component-1
Leave a comment below
