Problem Statement :-
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 < n
- a, b, c, and d are distinct.
- nums[a] + nums[b] + nums[c] + nums[d] == target
You may return the answer in any order.
Example
Input : nums = [1,0,-1,0,-2,2], target = 0
Result : [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
Solution 1
fix three pointers and look for the last one
nums = [1,0,-1,0,-2,2] ,target=0
nums = [1,0,-1,0,-2,2]
| | | < look for the last one >
i j k
step-1 sort the array nums and initialise an variable ans.
step-2 run three loops linearly for i, j, k pointers
1. find the last element, using binary search.
2. if the last element found then add the quadruplet toans
Java
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Set<List<Integer>> ans = new HashSet<List<Integer>>();
int n = nums.length;
Arrays.sort(nums);
for(int i=0; i<n; i++){
for(int j=i+1; j<n; j++){
for(int k=j+1; k<n; k++){
int x = target - (nums[i] + nums[j] + nums[k]);
if(Arrays.binarySearch(Arrays.copyOfRange(nums,k+1,n),x) >= 0){
List<Integer> r = new ArrayList<Integer>();
r.add(nums[i]);
r.add(nums[j]);
r.add(nums[k]);
r.add(x);
ans.add(r);
}
}
}
}
List<List<Integer>> result = new ArrayList<List<Integer>>();
for(List<Integer> list : ans){
result.add(list);
}
return result;
}
}
Top comments (0)