I am solving a problem. The problem is given below --
Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note:
The solution set must not contain duplicate quadruplets.
Given array nums = [-1,0,1,2,-1,-4], and target = -1.
A solution set is:
[[-4,0,1,2],[-1,-1,0,1]]
My code is given below for the that problem-
class Solution {
List<List<Integer>> output=new ArrayList();
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
for(int i=0;i<nums.length;i++){
if(i==0 || nums[i-1]!=nums[i]){
for(int j=i+1;j<nums.length;j++){
if(j==1 || nums[j-1]!=nums[j]){
calculate(nums, i, j, target);
}
}
}
}
return output;
}
public void calculate(int[] nums, int i, int j, int target){
Set<Integer> hashSet=new HashSet();
for(int k=j+1; k<nums.length;k++){
int vector=target-nums[i]-nums[j]-nums[k];
if(hashSet.contains(vector)){
output.add(Arrays.asList(nums[i], nums[j], nums[k],vector));
while(k+1<nums.length && nums[k]==nums[k+1]){
k++;
}
}
hashSet.add(nums[k]);
}
}
}
My output is: [[-4,0,2,1]]
But expected output is: [[-4,0,1,2],[-1,-1,0,1]]
Please help!
To solve this problem following steps I have performed..
A) For the main function:
1. Sort the input array nums.
2. Iterate through the array for 2 times (i, j):
If the current value is greater than zero, break from the
loop. Remaining values cannot sum to zero.
If the current value is the same as the one before, skip it.
Otherwise, call twoSum for the current position i.
B) For calculate function:
1. For each index k > j in A:
2. Compute complement vector = target -nums[i] - nums[j].
3. If complement exists in hashset seen:
4. We found a triplet - add it to the result res.
5. Increment k while the next value is the same as before to
avoid duplicates in the result.
C) Add nums[k] to hashset seen
D) Return the result output.
Problem is at line (j==1 || nums[j-1]!=nums[j]) & (i==0 || nums[i-1]!=nums[i])
static List<List<Integer>> output;
public static void main (String[] args) throws Exception{
output = new ArrayList<>();
fourSum(new int[]{0,0,0,0},0);
System.out.println(output);
}
public static void fourSum(int[] nums, int target) {
Arrays.sort(nums);
for(int i=0;i<nums.length;i++){
for(int j=i+1;j<nums.length;j++){
calculate(nums, i, j, target);
}
}
}
public static void calculate(int[] nums, int i, int j, int target){
Set<Integer> hashSet=new HashSet();
for(int k=j+1; k<nums.length;k++){
int vector=target-nums[i]-nums[j]-nums[k];
if(hashSet.contains(vector)){
output.add(Arrays.asList(nums[i], nums[j], nums[k],vector));
while(k+1<nums.length && nums[k]==nums[k+1]){
k++;
}
}
hashSet.add(nums[k]);
}
}
input:{0,0,0,0}, target:0, output: [[0,0,0,0]]
input:{-1,0,1,2,-1,-4}, target:-1, output: [[-4, 0, 2, 1], [-1, -1, 1, 0]]