public List<List<Integer>> threeSum(int[] num){
  List<List<Integer>> res=new ArrayList<>();
  Arrays.sort(num);
  for (int i=0; i < num.length - 2; i++) {
    if (i > 0 && num[i] == num[i - 1]) {
      continue;
    }
    if (num[i] > 0) {
      break;
    }
    int j=i + 1;
    int k=num.length - 1;
    while (j < k) {
      if (j > i + 1 && num[j] == num[j - 1]) {
        j++;
        continue;
      }
      if (num[i] + num[j] > 0) {
        break;
      }
      if (num[i] + num[j] + num[k] < 0) {
        j++;
      }
 else       if (num[i] + num[j] + num[k] > 0) {
        k--;
      }
 else {
        List<Integer> triplets=new ArrayList<>();
        triplets.add(num[i]);
        triplets.add(num[j]);
        triplets.add(num[k]);
        res.add(triplets);
        j++;
        k--;
      }
    }
  }
  return res;
}

public List < List < Integer > > threeSum ( int [ ] num ) { List < List < Integer > > res = new ArrayList < > ( ) ; Arrays . sort ( num ) ; for ( int i = 0 ; i < num . length - 2 ; i ++ ) { if ( i > 0 && num [ i ] == num [ i - 1 ] ) { continue ; } if ( num [ i ] > 0 ) { break ; } int j = i + 1 ; int k = num . length - 1 ; while ( j < k ) { if ( j > i + 1 && num [ j ] == num [ j - 1 ] ) { j ++ ; continue ; } if ( num [ i ] + num [ j ] > 0 ) { break ; } if ( num [ i ] + num [ j ] + num [ k ] < 0 ) { j ++ ; } else if ( num [ i ] + num [ j ] + num [ k ] > 0 ) { k -- ; } else { List < Integer > triplets = new ArrayList < > ( ) ; triplets . add ( num [ i ] ) ; triplets . add ( num [ j ] ) ; triplets . add ( num [ k ] ) ; res . add ( triplets ) ; j ++ ; k -- ; } } } return res ; }
two pointers . sort given array first . traverse the array with 1 pointer . use another 2 pointers from both start ( i + 1 ) and end to find the target . how to avoid duplicate ? compare current number with the previous one , if same , skip . how to early pruning ? when current number is positive , stop .
