Java: minor improve beats 95%


  • 5
    public class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            List<List<Integer>> res = new ArrayList<>();
            Arrays.sort(nums);  
            for(int i=0;i<nums.length-2;i++){
                // **if nums[i]>0 there is no chance to find three element giving the  sum of 0**
                if(nums[i]>0) break; 
                if(i>0 && nums[i]==nums[i-1])
                    continue;
                int low=i+1;
                int high=nums.length-1;
                int sum = -nums[i];
                while(low<high){
                    if(nums[low]+nums[high]==sum){
                        res.add(Arrays.asList(nums[i],nums[low],nums[high]));
                        while(low<high && nums[low]==nums[low+1]) low++;
                        low++;
                        while(low<high && nums[high]==nums[high-1]) high--;
                        high--;
                    }else if(nums[low]+nums[high]>sum){
                        while(low<high && nums[high]==nums[high-1]) high--;
                        high--;
                    }
                    else{
                        while(low<high && nums[low]==nums[low+1]) low++;
                        low++;
                    }
                        
                }
            }
            return res;
        }
    }

  • 2
    L

    very good idea! Another minor change could be replacing

    while(low<high && nums[low] == nums[low+1]) low++;
    low++;
    while(low<high && nums[high] == nums[high-1]) high--;
    high--;
    

    with:

    while(++low<high && nums[low] == nums[low-1]);
    while(low<--high && nums[high] == nums[high+1]);

  • 0

    I like this improvement.


  • 0

    what is interesting is when I edit the code as you suggested, it becomes slower and only beats 62.52%


  • 0
    L

    I think what it does is making the code cleaner. The reason it gets slower could be that someone comes up with faster solutions.


  • 0

    Not sure why. But my previous version still beat 95%. You can try it.


  • 0
    L

    I ran both versions several times. Their running times both ranges from 7ms to 9ms. So I think it is not a big problem.


Log in to reply
 

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