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: The solution set must not contain duplicate triplets.
For example, given array S = [-1, 0, 1, 2, -1, -4], A solution set is: [ [-1, 0, 1], [-1, -1, 2] ] public class Solution { public List<List<Integer>> threeSum(int[] num) { List<List<Integer>> res = new ArrayList<List<Integer>>(); if(num.length<3||num == null) return res; Arrays.sort(num); for(int i = 0; i <= num.length-3; i++){ if(i==0||num[i]!=num[i-1]){ //remove dupicate,相同的元素不必再取了，但是low,high,i可以指向不同元素相同值。 int low = i+1; int high = num.length-1; while(low<high){ int sum = num[i]+num[low]+num[high]; if(sum == 0){ List<Integer> unit = new ArrayList<Integer>(); unit.add(num[i]); unit.add(num[low]); unit.add(num[high]); res.add(unit); low++; high--; while(low<high&&num[low]==num[low-1])//remove dupicate low++; while(low<high&&num[high]==num[high+1])//remove dupicate high--; }else if(sum > 0) high --; else low ++; } } } return res; } }