4 Sum (Java)

	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:
	Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
	The solution set must not contain duplicate quadruplets.
	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)
	Solution: adopt 3 sum solution, and an extra for loop, because 3 sum soltuon is O(n^2), so this
	solution is O(n^3)
	"Don't forget skip duplicate"
	public class Solution {
	public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
	ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
	if (num.length<4){
	return result;
	}
	Arrays.sort(num);
	for (int i=0; i<num.length; i++){
	// skip duplicate
	if (i>0&& num[i]==num[i-1]){
	continue;
	}
	for (int j=i+1; j<num.length; j++){
	// skip duplicate
	if (j>i+1 &&num[j]==num[j-1]){
	continue;
	}
	int start=j+1;
	int end=num.length-1;
	while(start<end){
	int currentValue=num[i]+num[j]+num[start]+num[end];
	if(currentValue==target){
	ArrayList<Integer> current=new ArrayList<Integer>();
	current.add(num[i]);
	current.add(num[j]);
	current.add(num[start]);
	current.add(num[end]);
	result.add(current);
	// skip duplicate
	do {start++;} while(start<end&&num[start]==num[start-1]);
	do {end--;}while(start<end&&num[end]==num[end+1]);
	}
	else if(currentValue>target){
	end--;
	}
	else{
	start++;
	}
	}
	}
	}
	return result;
	}
	}

view raw 4 Sum.java hosted with ❤ by GitHub