😮454 4sum II

https://leetcode.com/problems/4sum-ii/

可以延申到k sum II，时间复杂度是O(n^(k/2))，思路是把数组们分成两半，算各自的sum的可能情况和出现频率，再结合到一起

class Solution {
    private int[][] allNums;
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        allNums = new int[][]{nums1, nums2, nums3, nums4};
        Map<Integer, Integer> left = sumCount(0, 1);
        Map<Integer, Integer> right = sumCount(2, 3);
        int ans = 0;
        for (int sum : left.keySet()) {
            ans += left.get(sum) * right.getOrDefault(-sum, 0);
        }
        return ans;
    }
    private Map<Integer, Integer> sumCount(int start, int end) {
        Map<Integer, Integer> cnt = new HashMap<>();
        // 初始状态，之后会像蜕壳一样更新
        cnt.put(0, 1);
        for (int i = start; i <= end; i++) {
            Map<Integer, Integer> tmpMap = new HashMap<>();
            int[] array = allNums[i];
            for (int total : cnt.keySet()) {
                for (int num : array) {
                    int newTotal = total + num;
                    // 记得加上之前已经有的newTotal的数量
                    tmpMap.put(newTotal, cnt.get(total) + tmpMap.getOrDefault(newTotal, 0));
                }
            }
            cnt = tmpMap;
        }
        return cnt;
    }
}