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:
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)
import java.util.ArrayList; import java.util.Arrays; public class Solution { public ArrayList<ArrayList<Integer>> fourSum(int[] num ,int target) { Arrays.sort(num); ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); HashSet<ArrayList<Integer>> hash = new HashSet<ArrayList<Integer>>(); for( int i = 0; i < num.length; i++){ for (int j = i+1; j < num.length; j++) { for (int k = j+1, l = num.length-1; k < l;) { int s = num[l] + num[i] + num[j] + num[k]; if (s == target) { ArrayList<Integer> x = new ArrayList<Integer>(); x.add(num[i]); x.add(num[j]); x.add(num[k]); x.add(num[l]); if(!hash.contains(x)){//remove duplicated list hash.add(x); result.add(x); } k++; l--; } else if (s > target) { l--; } else{ k++; } } } } return result; } }
public class Solution { public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) { Arrays.sort(num); ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); for(int i = 0 ; i < num.length -3 ; i++){ if(i>0 && num[i] == num[i-1]) continue; int temp = target - num[i]; int[] temp_array = Arrays.copyOfRange(num,i+1,num.length); ArrayList<ArrayList<Integer>> three = threeSum(temp_array,temp); for(ArrayList<Integer> list :three){ list.add(0,num[i]); result.add(list); } // result.addAll(three); } return result; } public ArrayList<ArrayList<Integer>> threeSum(int[] num,int target) { // Start typing your Java solution below // DO NOT write main() function Arrays.sort(num); ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); for(int i = 0; i < num.length -1 ;i++ ){ for(int j = i+1, k = num.length -1; j < k;){ ArrayList<Integer> x = new ArrayList<Integer>(); int s = num[i] + num[j] + num[k]; if( s == target){ x.add(num[i]); x.add(num[j]); x.add(num[k]); result.add(x); while(j +1< k && num[j] == num[j+1]){//skip duplicates j++; } j++; while(k -1>j && num[k] == num[k-1]){ k--; } k--; } else if(s<target){ j++; } else{ k--; } } while(i +1 < num.length && num[i] == num[i+1]){ i++; } } return result; } }