454. 4Sum II

二刷 06/2022

Version #2 K Sum II

本来以为挺简单的没想到其实有一些重点是想不到的

第一个就是如何用recursion来收集所有可能的sum，每一层都试着加入当前这个array所有的数，是O(N) time，k/2 层就是  O(N^(k / 2))

第二个非常重要就是一直TLE的reason是我把所有array分成了[0, length / 2]和[length /  2 + 1, length - 1] 两个部分，这样的分配是不均匀的，譬如当array数是4的时候就会分成[0, 1, 2]和[3]造成复杂度从O(N^2)飚到O(N^3)

为了平均分配应该是[0, length / 2 - 1]和[length / 2, length - 1]

Space O(k / 2) for recursion, O(N^(k/2)) for hashmap -> Total O(N^(k/2))

Runtime: 184 ms, faster than 58.71% of Java online submissions for 4Sum II.

Memory Usage: 57.3 MB, less than 59.43% of Java online submissions for 4Sum II.

class Solution {

    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {

        return kSumCount(new int[][]{nums1, nums2, nums3, nums4});

    }

    

    private int kSumCount(int[][] nums) {

        Map<Integer, Integer> firstHalfSums = new HashMap<>();

        countSum(nums, 0, nums.length / 2  - 1, 0, firstHalfSums);

        return countComplement(nums, nums.length / 2, nums.length - 1, 0, firstHalfSums);

    }

    

    private void countSum(int[][] nums, int start, int end, int sum, Map<Integer, Integer> sums) {

        if (start > end) {

            sums.put(sum, sums.getOrDefault(sum, 0) + 1);

            return;

        }

        for (int a : nums[start]) {

            countSum(nums, start + 1, end, sum + a, sums);

        }

    }

    

    private int countComplement(int[][] nums, int start, int end, int sum, Map<Integer, Integer> sums) {

        if (start > end) {

            return sums.getOrDefault(-sum, 0);

        }

        int cnt = 0;

        for (int a : nums[start]) {

            cnt += countComplement(nums, start + 1, end, sum + a, sums);

        }

        return cnt;

    }

}

一刷 05/2022

Version #1 HashMap

Time O(n^2)

Space O(n^2)

Runtime: 189 ms, faster than 44.39% of Java online submissions for 4Sum II.

Memory Usage: 58.3 MB, less than 33.53% of Java online submissions for 4Sum II.

class Solution {

    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {

        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0 || nums3 == null || nums3.length == 0 || nums4 == null || nums4.length == 0) {

            return 0;

        }

        // nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

        // nums3[k] + nums4[l] = - (nums1[i] + nums2[j])

        // add all possible minus sum of nums1 and nums2 to a hashmap

        Map<Integer, Integer> target = new HashMap<>();

        for (int num1 : nums1) {

            for (int num2 : nums2) {

                target.put(num1 + num2, target.getOrDefault(num1 + num2, 0) + 1);

            }

        }

        int cnt = 0;

        for (int num3 : nums3) {

            for (int num4 : nums4) {

                cnt += target.getOrDefault(-num3-num4, 0);

            }

        }

        return cnt;

    }

}