3Sum problem java solution


  • 0
    N
    
    class Solution {
        //remember 2 sum problem, we just fix one element and perform 2 sum problem for getting other 2 elements
        public List<List<Integer>> threeSum(int[] nums) {        
            List<List<Integer>> res=new ArrayList<List<Integer>>();
            if(nums.length<3)//no triplets
                return res;
            Arrays.sort(nums);
            for(int i=0;i<nums.length-2;i++){//fix the first element  
                if(i==0 || nums[i]!=nums[i-1]){//skip dups
                    int l=i+1;
                    int r=nums.length-1;
                    while(l<r){
                        if((nums[l]+nums[r]+nums[i])==0){
                            res.add(new ArrayList<Integer>(Arrays.asList(nums[i],nums[l],nums[r])));                        
                            l=moveLeftPointer(l,r,nums);
                            r=moveRightPointer(l,r,nums);
                        }else if((nums[l]+nums[r]+nums[i])<0){                        
                            l=moveLeftPointer(l,r,nums);           
                        }else{ //>0
                            r=moveRightPointer(l,r,nums);                                             
                        }
                    }
                }
            }
            return res;
        }  
        
        int moveLeftPointer(int l,int r,int[] nums){
            do{
                l++;
            }while(l<r && nums[l]==nums[l-1]);//avoid dups IMP step
            return l;
        }
        
        int moveRightPointer(int l,int r,int[] nums){
            do{
               r--;
             }while(l<r && nums[r]==nums[r+1]);//avoid dups IMP step  
            return r;
        }
    }
    

Log in to reply
 

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