3 Sum

	Time: O(n^2)
	Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0?
	Find all unique triplets in the array which gives the sum of zero.
	Note:
	Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ? b ? c)
	The solution set must not contain duplicate triplets.
	public class Solution {
	public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
	// Start typing your Java solution below
	// DO NOT write main() function
	ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
	if (num.length<3) return result;
	Arrays.sort(num);
	for (int i=0; i<num.length; i++){
	if (i>0){
	if (num[i]==num[i-1]){
	continue;
	}
	}
	int start=i+1;
	int end=num.length-1;
	while(start<end){
	int sum=num[i]+num[start]+num[end];
	if (sum>0){
	end--;
	}
	else if (sum<0){
	start++;
	}
	else{
	ArrayList<Integer> current=new ArrayList<Integer>();
	current.add(num[i]);
	current.add(num[start]);
	current.add(num[end]);
	result.add(current);
	do {start++;} while(start<end&&num[start]==num[start-1]);
	do {end--;} while(start<end&&num[end]==num[end+1]);
	}
	}
	}
	return result;
	}
	}

view raw 3Sum.java hosted with ❤ by GitHub