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] ] 把所有满足条件的三元组都要列出来！
思路：先排序，比如先把第一个元素定为nums[i]时，让后面两个元素和为(-1)*nums[i]，转化为两元素和的问题。 遇到相同的元素就跳过去！
public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> my = new ArrayList<>(); Arrays.sort(nums); for(int i=0;i<=nums.length-3;i++) if(nums[i]<=0){ if(i>=1 && nums[i]==nums[i-1]) continue; int j=i+1; int k=nums.length -1; while(j<k){ if(nums[i]+nums[j]+nums[k]==0) { List<Integer> one = new ArrayList<>(); one.add(nums[i]); one.add(nums[j]); one.add(nums[k]); my.add(one); j++; k--; while(j<k && nums[j]==nums[j-1]) j++; while(j<k && nums[k]==nums[k+1]) k--; } else { boolean flag =true; // 求有序数组中两个数的和为(-1)*nums[i] while(flag){ while(j<k && nums[j]+nums[k]>(-1)*nums[i]) k--; while(j<k && nums[j]+nums[k]<(-1)*nums[i]) j++; if( j>=k || nums[j]+nums[k]==(-1)*nums[i]) flag = false; } } } // while(j<k) } return my; }