One hash map and one double loop


  • 0
    A

    It is O(n^3) time complexity and O(n^2) space complexity. But besides adding the 4sums to the list, the search part is O(n^2) time-complexity. So in case we have less than O(n^2) lists of 4 sums it is O(n^2).

    public class Solution {
        public List<List<Integer>> fourSum(int[] nums, int target) {
            List<List<Integer>> ans = new ArrayList<List<Integer>>();
            if (nums.length < 4) return ans;
            Arrays.sort(nums);
            // boundary case
            if (target % 4==0) {
                int a = target/4;
                for (int l = 0; l < nums.length; l++) {
                    if (nums[l] == a && l+3 < nums.length && nums[l] == nums[l+3]){
                        ans.add(new ArrayList<Integer>(Arrays.asList(a, a, a, a)));
                        break;
                    }
                }
            }
            Map<Integer, ArrayList<Integer>> twoSumMap = new HashMap<>();
            int i = 0;
            // We traverse all pairs (i, j) for i < j and (nums[i], nums[j]) distinct. 
            // Check if (nums[i], nums[j]) can be the third and fourth number in the 4 sum. If so, add them
            // Put (nums[i], nums[j]) in a Hashmap that stores all possible first and second number in the 4 sum.
            // In order to keep as much information as possible, we use nums[i] + nums[j] as the key in the hashmap
            // and the first index i for nums[i] as the value. 
            // It has the property that if x = nums[map.get(sum)] and y = sum - x, then x <= y 
            // and the pair (x, y) is not repeated
            
            while (i < nums.length) {
                int j = i+1;
                while (j < nums.length) {
                    int sum = nums[i] + nums[j];
                    if (2*sum > target && twoSumMap.containsKey(target - sum)) {
                        add(i, j, target, nums, twoSumMap, ans);
                    }
                    if (twoSumMap.containsKey(sum)) {
                        twoSumMap.get(sum).add(i);
                    } else {
                        twoSumMap.put(nums[i] + nums[j], new ArrayList<Integer>(Arrays.asList(i)));
                    }
                    j = getLastIndex(j, nums);
                    j++;
                }
                i = getLastIndex(i, nums);
                i++;
            }
            return ans;
        }
        // a1, a2, a3, a4 are the four numbers in the 4sum. 
        // Check that they are not duplicated before adding them to the list. 
        // The only possibly duplicated cases are a1 < a2 = a3 < a4. a1 = a2 = a3 < a4 or a1 < a2 = a3 = a4 
        private void add(int i, int j, int target, int[] nums, Map<Integer, ArrayList<Integer>> map, List<List<Integer>> list) {
            int a3 = nums[i], a4 = nums[j], x = target - a3 - a4;
            ArrayList<Integer> lx = map.get(x);
            for (Integer i1 : lx) {
                int a1 = nums[i1], a2 = x - a1;
                if (a2 < a3) list.add(new ArrayList<Integer>(Arrays.asList(a1, a2, a3, a4)));
                else if (a2 == a3) {
                    if (a1 == a3 || a2 == a4) {
                        if (i+2 < nums.length && nums[i] == nums[i+2])
                            list.add(new ArrayList<Integer>(Arrays.asList(a1, a2, a3, a4)));
                    } else if (i+1 < nums.length && nums[i] == nums[i+1])
                        list.add(new ArrayList<Integer>(Arrays.asList(a1, a2, a3, a4)));
                }
            }
        }
        // given i in the sorted array a, get the last index j such that a[j] = a[i]
        private int getLastIndex(int i, int[] a) {
            while (i+1 < a.length && a[i] == a[i+1]) i++;
            return i;
        }
    }
    

Log in to reply
 

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