Easy java solution with N times two pointer search


  • 0
    Z
    /**
     * 1.Sort.
     * 2.For each element, run two pointer search in ordr to find element + two values == 0
     * 3.Avoid duplicates: in each element; in 2 pointer search.
     * 4.Guard array index : left < right
     * 
     * nlogn + n elemtn * O(n) each two pointer = O(n^2)
     */
    public class Solution {
        public List<List<Integer>> threeSum(int[] ns) {
            List<List<Integer>> ret = new ArrayList<>();
            if(ns == null || ns.length <= 2)
                return ret; 
            
            // sort
            Arrays.sort(ns);
            
            // n times:  two pointers search.
            for(int i =0; i < ns.length -2 ; i++){
                int min = ns[i];
                // min is largerthan zero, therefore sum is larger than zero, cannot be == 0
                if(min >0)
                    break;
                    
                // skip duplicates.
                if(i >0 && ns[i-1] == ns[i])
                    continue;
                    
                // two pointer search
                int left = i +1; 
                int right = ns.length -1;
                while(left < right){
                    int sum = min + ns[left] + ns[right];
                    if(sum == 0){
                        // accumulate ret
                        ret.add(Arrays.asList(min, ns[left], ns[right]));
                        /* avoid duplicate;*/
                        while(left < right && ns[left] == ns[left +1])
                            left ++;
                        while(left < right && ns[right] == ns[right -1])
                            right --;
                    }
                    if(sum >0){ 
                        // decrease sum
                        right --;
                    }
                    else{ 
                        // increase sum
                        left ++;
                    }
                }
            }
            
            return ret;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.