Clean, Actually Readable Java Solution Based on 3Sum O(n^3)


  • 0
    A
    // O(n^3) Based on 3Sum
        public List<List<Integer>> fourSum(int[] nums, int target) {
            List<List<Integer>> results = new ArrayList<>();
            
            Arrays.sort(nums);
            
            for (int i = 0; i < nums.length-3; i++) {
                // skip dup at every step
                if (i > 0 && nums[i] == nums[i-1]) continue;
                
                List<List<Integer>> quads = threeSum(nums, i, target - nums[i]);
                results.addAll(quads);
            }
            return results;
        }
        
        // General 3Sum
        public List<List<Integer>> threeSum(int[] nums, int ind, int target) {
            List<List<Integer>> results = new ArrayList<>();
            
            for (int a = ind+1; a < nums.length-2; a++) {
                if (a > ind+1 && nums[a] == nums[a-1]) continue;
    
                for (int b = a+1, c = nums.length-1; b < nums.length-1 && c > b; b++) {
                    if (b > a+1 && nums[b] == nums[b-1]) continue;
                    
                    int ab = nums[a] + nums[b];
                    int diff = target - ab;
                    
                    if (nums[c] < diff) continue;
                    
                    while (nums[c] > diff && c > b+1) c--;
                    
                    if (nums[c] == diff) {
                        results.add(Arrays.asList(nums[ind], nums[a], nums[b], nums[c]));
                    }
                }
            }
            return results;
        }
    

Log in to reply
 

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