3Sum - LeetCode - Tec BarTec Bar

Problem
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


public class Solution {
    public List<List<Integer>> threeSum(int[] num) {
    	List<List<Integer>> lsts = new ArrayList<List<Integer>>();
    	if(num.length < 3) return lsts;
    	
    	Arrays.sort(num);
    	
    	for(int i = 0; i < num.length - 2 && num[i] <= 0; i++) {
    		if(i == 0 || num[i-1] < num[i]) {  // make sure 1st number used once
    			int m = i+1;
    			int n = num.length -1;
    			while(m < n) {
    				int sum = num[i] + num[m] + num[n];
    				if(sum == 0) {
    					List<Integer> lst = new ArrayList<Integer>();
    					lst.add(num[i]);lst.add(num[m]);lst.add(num[n]);
    					lsts.add(lst);
    					m++; n--;
    					while(n > m && num[n] == num[n + 1]) {
    						n--;  // until find next different top number
    					}
    					while(n > m && num[m] == num[m - 1]) {
    						m++;  // until find next different lower number
    					}
    				} else if(sum > 0) { // the top number is too big, move down one #
    					n--;
    				} else { // the lower number is too small, check next #
    					m++;
    				}
    			}
    		}
    	}
    	
    	return lsts;
    }
}