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.
For example, given array S = {-1 0 1 2 -1 -4},
A solution set is:
(-1, 0, 1)
(-1, -1, 2)
sort the array
one out loop for the first element ( careful about the duplicate)
inside the loop, two pointers from two-end to middle
edgecase
nums == null ?
nums.length == 0?
Note:
avoid duplicate
public List<List<Integer>> threeSum(int[] nums){ List<List<Integer>> res = new ArrayList<List<Integer>>(); if(nums == null || nums.length == 0) return res; Arrays.sort(nums); for(int i = 0; i < nums.length; i++){ if(i>0 && nums[i] == nums[i-1]) continue; int j = i+1; int k = nums.length-1; while(j<k){ int sum = nums[i] + nums[j] + nums[k]; if(sum == 0){ List<Integer> one = new ArrayList<Integer>(); one.add(nums[i]); one.add(nums[j]); one.add(nums[k]); res.add(one); while(j <k && nums[j] == nums[j+1]){ j++; } j++; while(j<k && nums[k] == nums[k-1]){ k--; } k--; } else if(sum > 0){ k--; } else{ j++; } } } return res; }
原文：http://www.cnblogs.com/momoco/p/4849062.html