454. 四数相加 II

解题思路

• 暴力解法--超时
  1.分析题意可知，四个数组的长度相等，所以最直接的解法，就是四个for循环
  2.找到满足条件的数据，则result++
  （四重for循环--超时）
  （两重for循环三次--依然超时）

• 哈希映射解法
  1.先遍历A+B数组的结果，保存在map中，key为a+b的值，value为出现的次数
  2.遍历C+D数组，同时做判断，如果c+d的相反值，在map中出现过，则将map中对应的value，add 到result中

解题遇到的问题

1.哈希解法的关键点在于，如何将问题简化，首先需要想到四重for循环到双重循环的简化
2.其次，需要设计，key、value的对应值，分别是什么？

后续需要总结学习的知识点

哈希解法的总结

##解法1--超时
class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3,
            int[] nums4) {
        int result = 0;
        int k = 0;
        int[] a1 = new int[(int) Math.pow(nums1.length, 2)];
        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                a1[k++] = nums1[i] + nums2[j];
            }
        }

        k = 0;
        int[] a2 = new int[(int) Math.pow(nums1.length, 2)];
        for (int i = 0; i < nums3.length; i++) {
            for (int j = 0; j < nums4.length; j++) {
                a2[k++] = nums3[i] + nums4[j];
            }
        }

        for (int i = 0; i < a1.length; i++) {
            for (int j = 0; j < a2.length; j++) {
                if (a1[i] + a2[j] == 0) {
                    result++;
                }
            }
        }
        return result;
    }
}

##解法2--正确
class Solution {
    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
        Map<Integer, Integer> countAB = new HashMap<Integer, Integer>();
        for (int u : A) {
            for (int v : B) {
                countAB.put(u + v, countAB.getOrDefault(u + v, 0) + 1);
            }
        }
        int ans = 0;
        for (int u : C) {
            for (int v : D) {
                if (countAB.containsKey(-u - v)) {
                    ans += countAB.get(-u - v);
                }
            }
        }
        return ans;
    }
}