*Java* a little bit faster than other common methods (9ms, beats 95%)


  • 23
    E

    To avoid duplicate list items, I skip unnecessary indices at two locations:

    • one at the end of the outer loop (i-loop)
    • the other at the end of the inner loop (j-loop).

    To avoid useless computations, the following is kind of critical:

    • the function return immediately when nums[i]*4 > target
    • the inner loop break immediately when nums[j]*4 < target.

    These two lines save quite some time due to the set up of the test cases in OJ.

    public class Solution {
        public List<List<Integer>> fourSum(int[] nums, int target) {
            List<List<Integer>> list = new ArrayList<List<Integer>>();
            Arrays.sort(nums);
            int second = 0, third = 0, nexti = 0, nextj = 0;
            for(int i=0, L=nums.length; i<L-3; i++) {
                if(nums[i]<<2 > target) return list; // return immediately
                for(int j=L-1; j>i+2; j--) {
                    if(nums[j]<<2 < target) break; // break immediately
                    int rem = target-nums[i]-nums[j];
                    int lo = i+1, hi=j-1;
                    while(lo<hi) {
                        int sum = nums[lo] + nums[hi];
                        if(sum>rem) --hi;
                        else if(sum<rem) ++lo;
                        else {
                            list.add(Arrays.asList(nums[i],nums[lo],nums[hi],nums[j]));
                            while(++lo<=hi && nums[lo-1]==nums[lo]) continue; // avoid duplicate results
                            while(--hi>=lo && nums[hi]==nums[hi+1]) continue; // avoid duplicate results
                        }
                    }
                    while(j>=1 && nums[j]==nums[j-1]) --j; // skip inner loop
                }
                while(i<L-1 && nums[i]==nums[i+1]) ++i; // skip outer loop
            }
            return list;
        }
    }

  • 0
    Z

    Unnecessary line:
    int second = 0, third = 0, nexti = 0, nextj = 0;


Log in to reply
 

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