Leetcode 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:

• 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)

Solution 1: Sort the Array, i,j,k will be one solution. When i iterate through the array, solve 2 sum from i+1 to end. Pay attention that result need to be unique.

 public class Solution {  
   public List<List<Integer>> threeSum(int[] nums) {  
     int n=nums.length;  
     List<List<Integer>> res=new ArrayList<>();  
     if (n<=2) return res;  
     Arrays.sort(nums);  
     if (nums[0]>0 || nums[n-1]<0) return res;  
     for (int i=0; i<n-2; i++) {  
       if (i>0 && nums[i]==nums[i-1]) continue;//to keep unique  
       int lo=i+1, hi=n-1;  
       while (lo<hi) {  
         int num=nums[i]+nums[lo]+nums[hi];  
         if (num>0) hi--;  
         else if (num<0) lo++;  
         else {  
           List<Integer> one=new ArrayList<>();  
           res.add(Arrays.asList(nums[i],nums[lo],nums[hi]));  
           //to keep nunique, lo go to next non-repeat one  
           int k=lo+1;  
           while (k<hi && nums[k]==nums[lo]) k++;  
           lo=k;  
         }  
       }  
     }  
     return res;  
   }  
 }