.png)
Given an array nums of n integers, return an array of all the distinct 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
Your answer doesn't matter in what 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
Following are the detailed steps.
- Sort the input array.
- Fix the first element as A[i] where i is from 0 to n–3. After fixing the first element of quadruple, fix the second element as A[j] where j varies from i+1 to n-2. Find the remaining two elements in O(n) time, using method 1 of this post.
.png)
𝐂++ 𝐒𝐎𝐋𝐔𝐓𝐈𝐎𝐍
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, long target) {
vector<vector<int>> res;
if(nums.empty())
return res;
int n=nums.size();
sort(nums.begin(),nums.end());
for(int i=0; i<n; i++){
for(int j=i+1; j<n; j++){
long target_2=target-nums[i]-nums[j];
int s=j+1;
int e=n-1;
while(s<e){
long twosum=nums[s]+nums[e];
if((twosum)<target_2) s++;
else if(twosum>target_2) e--;
else{
vector<int> quadruplet(4,0);
quadruplet[0]=nums[i];
quadruplet[1]=nums[j];
quadruplet[2]=nums[s];
quadruplet[3]=nums[e];
res.push_back(quadruplet);
while(s<e && nums[s]==quadruplet[2]) ++s;
while(s<e && nums[e]==quadruplet[3]) --e;
}
}
while(j+1<n && nums[j+1]==nums[j]) ++j;
}
while(i+1<n && nums[i+1]==nums[i]) ++i;
}
return res;
}
};
JAVA SOLUTION
class Solution {
public List<List<Integer>> fourSum(int[] nums, long target) {
ArrayList<List<Integer>> res=new ArrayList<List<Integer>>();
if(nums==null || nums.length==0)
return res;
int n=nums.length;
Arrays.sort(nums);
for(int i=0; i<n; i++){
for(int j=i+1; j<n; j++){
long target_2=target-nums[i]-nums[j];
int s=j+1;
int e=n-1;
while(s<e){
long two_sum=nums[s]+nums[e];
if(two_sum<target_2) s++;
else if(two_sum>target_2) e--;
else{
List<Integer> quad=new ArrayList();
quad.add(nums[i]);
quad.add(nums[j]);
quad.add(nums[s]);
quad.add(nums[e]);
res.add(quad);
while(s<e && nums[s]==quad.get(2)) ++s;
while(s<e && nums[e]==quad.get(3)) --e;
}
}
while(j+1<n && nums[j+1]==nums[j]) ++j;
}
while(i+1<n && nums[i+1]==nums[i]) ++i;
}
return res;
}
}
Success
Details Runtime: 89 ms, faster than 69.95% of C++ online submissions for 4Sum.
Memory Usage: 13 MB, less than 99.40% of C++ online submissions for 4Sum.