JAVA O(n^2) Solution by reducing 4SUM to 3SUM


  • -1
    B
    public class Solution {
    
        public List<List<Integer>> fourSum(int[] nums, int target) {
            List<List<Integer>> res = new ArrayList<List<Integer>>();
    
            if (nums == null || nums.length < 4) {
                return res;
            }
            
            Arrays.sort(nums);
            int len = nums.length;
            
            if (nums[0] * 4 > target || nums[len - 1] * 4 < target) {
                return res;
            }
            
            int n;
            for (int i = 0; i < len; i ++) {
                n = nums[i];
                if (i > 0 && n == nums[i - 1]) continue;
                if (n + 3 * nums[len - 1] < target) continue;
                if (4 * n > target) break;
                if (4 * n == target) {
                    if (i + 3 < len && nums[i + 3] == nums[i]) {
                        res.add(Arrays.asList(n,n,n,n));
                    }
                    break;
                }
    
                int [] subSum = Arrays.copyOfRange(nums, i + 1, len);
                List<List<Integer>> rem = threeSum(subSum, target - n);
                
                if (rem.size() != 0) {
                    for (List<Integer> subList : rem) {
                        List<Integer> temp = new LinkedList<Integer>(subList);
                        temp.add(0, n);
                        res.add(temp);
                    }
                }
            }
            
            return res;
        }
        
       //3Sum: O(n), because not need to Arrays.sort again in this method;
        public List<List<Integer>> threeSum(int[] nums, int target) {
            List<List<Integer>> res = new ArrayList<>();
            
            if (nums == null || nums.length == 0) {
                return res;
            }
            
            // Arrays.sort(nums);
            
            int sum;
            int lo,hi;
            
            for (int i = 0; i < nums.length - 2; i ++) {
                if (i > 0 && nums[i] == nums[i - 1]) {
                    continue;
                }
                sum = target - nums[i];
                
                lo = i + 1;
                hi = nums.length - 1;
                
                while (lo < hi) {
                    if (nums[lo] + nums[hi] == sum) {
                        res.add(Arrays.asList(nums[i], nums[lo], nums[hi]));
                        
                        while (lo < hi && nums[lo] == nums[lo + 1]) lo++;
                        while (hi > lo && nums[hi] == nums[hi - 1]) hi--;
                        
                        lo++;
                        hi--;
                    }else if (nums[lo] + nums[hi] < sum) {
                        lo ++;
                    }else {
                        hi --;
                    }
                }
            }
            return res;
        }
    }
    

  • 0
    R

    threeSum is still O(n^2) not O(n)
    So it is O(n^3)


Log in to reply
 

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