15. 3Sum 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> threeSum(int[] num) { List> result = new ArrayList>(); if(num==null || num.length<3) return result; Arrays.sort(num); for(int i=0; i0 && num[i]==num[i-1]) continue; int left = i+1; int right = num.length - 1; while(left r = new ArrayList(); r.add(num[i]); r.add(num[left]); r.add(num[right]); result.add(r); left++; right--; while(leftleft && num[right]==num[right+1]) right--; } else if(sum < -num[i]) { left++; } else { right--; } } } return result; } }