37lines O(n3) beats 99.16% of java submission


  • 0
    J
    public class Solution {
        public List<List<Integer>> fourSum(int[] nums, int target) {
            List<List<Integer>> res = new LinkedList<>(); 
            // we sort the arrays O(n log(n));
            Arrays.sort(nums);
            // from i = 0, to i - 3 possibilities
            for(int i=0; i< nums.length - 3; i++) {
                // we check repetition and boundaries.
                if(i > 0 && nums[i-1] == nums[i] 
                   || nums[i] * 4 > target 
                   || nums[nums.length-1]*3 + nums[i] < target) continue;
                threeSum(nums, i+1, nums[i], target, res);
            }
            return res;
        }
        
        public void threeSum(int[] num, int start, int value, int target, List<List<Integer>> res) {
            for(int i = start; i < num.length ;i++) {
                // we check boundaries and repetitions
                if(value + num[i] + 2 * num[num.length-1] < target 
                   || value + num[i] * 3 > target 
                   || (i > start && num[i-1] == num[i])) continue;
                int j = i+1, k = num.length-1;
                while(j < k) {
                    if(value+num[j]+num[k]+num[i] == target) {
                        res.add(Arrays.asList(value, num[i], num[j], num[k]));
                        while (j < k && num[j] == num[j+1]) j++;
                        while (j < k && num[k] == num[k-1]) k--;
                        j++; k--;
                    }
                    // We shift the two pointers until we have a new == 0, we stop if j==k
                    while(j < k && (value+num[j]+num[k]+num[i] < target)) j++; 
                    while(j < k && (value+num[j]+num[k]+num[i] > target)) k--;
                }
            }
        }
    }
    

Log in to reply
 

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