（哈希表）Java 求解四数相加 II

灰太狼 2023-01-18 14:23 56阅读 0赞

### 文章目录 ###

*   *  一、题目
     *  二、hash 解法
     *  三、代码
     *  四、总结

## 一、题目 ##

给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 `A[i] + B[j] + C[k] + D[l] = 0`

为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在  − 2 28 -2^\{28\} −228 到  2 28 − 1 2^\{28\} - 1 228−1 之间，最终结果不会超过  2 31 − 1 2^\{31\} - 1 231−1

## 二、hash 解法 ##

题目是四个独立的数组，找到：`A[i] + B[j] + C[k] + D[l] = 0`

我们可以先统计两个数组的和的情况，然后存放到map中，key为对应的和，值为该和出现的次数

然后再统计剩余两个数组出现和的情况，在map中寻找是否存在相加为0的情况，同时记录总的次数

## 三、代码 ##

class Solution { 
        public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) { 
            Map<Integer, Integer> map = new HashMap<>();
            int temp;
            int res = 0;
            //统计两个数组中的元素之和，同时统计出现的次数，放入map
            for (int i : nums1) { 
                for (int j : nums2) { 
                    temp = i + j;
                    if (map.containsKey(temp)) { 
                        map.put(temp, map.get(temp) + 1);
                    } else { 
                        map.put(temp, 1);
                    }
                }
            }
            //统计剩余的两个元素的和，在map中找是否存在相加为0的情况，同时记录次数
            for (int i : nums3) { 
                for (int j : nums4) { 
                    temp = i + j;
                    if (map.containsKey(0 - temp)) { 
                        res += map.get(0 - temp);
                    }
                }
            }
            return res;
        }
    }

## 四、总结 ##

hash 表思想：在集合中查找一个元素是否出现