HashMap的应用

发表于 分类于 ， Valine：

对于数据结构 HashMap/HashSet，它不仅可以用于去重，还可以用于快速查找（复杂度 O(1)）。针对查找功能，整理了下面几道题目，用于体会其用法。

具体的，我们首先对几道题目进行分析，给出代码，最后统一的进行总结。

题1- 两数之和

题目：给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。LeetcodeLink

分析：这道题目最简单的做法是直接进行暴力枚举，使用两重 for 循环寻找枚举所有的两数之和，再判断和是否为目标 target，这样的算法时间复杂度为 O(n^2)。降低时间复杂度的方法是转换枚举答案的思维，而是将问题转为 已知两数之和 target 和其中 一个整数 x1，求解另一个数字 x2，从而将问题变为寻找特定数字的问题。具体编程中，我们可以在遍历的同时，将遍历到的数字放入到 HashMap 中，key 值为数值量，value 值为该数字在数组中位置的下标。参考如下的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        // 遍历过程中，将已经遍历过的元素放置到 HashMap 中
        for(int i = 0; i < nums.length; ++i){
            int x1 = nums[i];
            if(map.containsKey(target-x1)){
                return new int[]{i, map.get(target-x1)};
            }
            map.put(x1, i);
        }
        return new int[2];
    }
}

题2- 和相同的二元子数组

题目：给你一个二元数组 nums (数组中不是0就是1)，和一个整数 goal ，请你统计并返回有多少个和为 goal 的 非空 子数组。(子数组 是数组的一段连续部分。) leetcodeLink

分析：与上一题类似，本题也是寻找 “和为特定值” 的数据。但与上一题不同的是，本题不再是寻找两个数字的和为特定值，而是寻找一个区间的和为特定值。对于区间和 sum[a, b), 实际上可以写成两个前缀和的差值的形式，即 sum[a, b) = sum[0,b) - sum[0, a)。因此，类似的，本题可以将 原问题转换为 知道两个前缀区间和的差值 goal 与一个前缀区间和 x, 求 前缀区间 x 前面的满足前缀和等于 x-goal 的区间。具体的，我们可以在遍历数组的同时，将前缀和放置在 HashMap 中，key 值为前缀和的值，value 值为该前缀和出现的次数。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int numSubarraysWithSum(int[] nums, int goal) {
        // 将前缀和信息放置在 HashMap 中。key 为前缀和的值，value 为该和出现的次数
        Map<Integer, Integer> preSum = new HashMap<>();
        preSum.put(0, 1);

        // 遍历时记录的前缀和
        int tmpSum = 0;
        int ans = 0;
        for (int i = 0; i < nums.length; i++) {
            tmpSum += nums[i];
            ans += tmpSum - goal >= 0 ? preSum.getOrDefault(tmpSum-goal, 0) : 0;
            preSum.put(tmpSum, preSum.getOrDefault(tmpSum, 0)+1);
        }
        return ans;
    }
}

由于本题数据的特殊性，数组中的数值只有 0 和 1，因此 前缀和一定是连续的整数。根据 key 值的特殊性，我们可以使用 数组 来实现 HashMap 的效果。具体地，数组的下标等效于 key 值，value 值为对应前缀和出现的次数。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int numSubarraysWithSum(int[] nums, int goal) {
        // 使用 stream 进行处理: public static IntStream stream​(int[] array)
        int sum = Arrays.stream(nums).sum();
        // 等效 HashMap
        int[] preSum = new int[sum+1];
        preSum[0] = 1;

        int tmpSum = 0, ans = 0;
        for (int num : nums) {
            tmpSum += num;
            ans += tmpSum - goal >= 0 ? preSum[tmpSum-goal] : 0;
            preSum[tmpSum]++;
        }
        return ans;
    }
}

题3- 大餐计数

题目：大餐 是指 恰好包含两道不同餐品 的一餐，其美味程度之和等于 2 的幂。给你一个整数数组 deliciousness ，其中 deliciousness[i] 是第 i​​​​​​​​​​​​​​ 道餐品的美味程度，返回你可以用数组中的餐品做出的不同 大餐 的数量。结果需要对 1e9 + 7 取余。注意，只要餐品下标不同，就可以认为是不同的餐品，即便它们的美味程度相同。链接

分析: 与求解 “两数之和” 类似，本题要求的也是 两数之和 为特定值。只不过这里的特定值不是一个值，而是一类值：2的整数次幂。整体的思路实际上是相同的，首先将数据放置到 HashMap 中，key值为“美味值”，value 值则为对应美味值出现的次数。由于存在多个目标值，遍历到数值 x 时，我们要枚举各个目标和 target，来寻找不同的 target - x。此外，一些需要注意的细节包括：

  • 需要根据两个加数（美味值）是否相同分类进行讨论；
  • 当两个加数不相同时，可能出现重复计算，我们可以在判断条件中添加 两个加数之间的大小关系要求，来避免重复。

具体参考下面的代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    public int countPairs(int[] deliciousness) {
        final int MOD = 1_000_000_007;

        // 美味和 对应 2的k次幂，分析k可能的最大值
        // IntStream 的 max() 方法返回值为 OptionalInt 类型。
        // 由于这里的 deliciousness length 长于0，故 max() 值一定存在，直接 getAsInt() 即可
        int max = Arrays.stream(deliciousness).max().getAsInt();

        // Map 中存放 deliciousness 的信息, key 值美味值，value 值为 key 值出现的次数
        Map<Integer, Integer> map = new HashMap<>();
        for(int delicious : deliciousness){
            map.put(delicious, map.getOrDefault(delicious, 0)+1);
        }
        
        long res = 0;
        for(Integer delicious : map.keySet()){
            int sum = 1;
            long count1 = map.get(delicious);
            for(int i = max * 2; i > 0; i >>= 1){
                int anOtherDish = sum - delicious;
                // 设置条件 anOtherDish >= delicious, 避免重复计算
                if(anOtherDish >= delicious && map.containsKey(anOtherDish)){
                    // 分两种情况: 情况1- 两个美味值相同；情况2- 两个美味值不相同
                    if(anOtherDish == delicious){
                        res += count1 * (count1-1) / 2;
                    }else{
                        long count2 = map.get(anOtherDish);
                        res += count1 * count2;
                    }
                    res = res % MOD;
                }
                sum <<= 1;
            }
        }
        return (int)res;
    }
}

总结

上面的三道例题 都使用了 HashMap 来实现快速查找的目的。题1 是最为经典的模型，即求一组数中，和为固定值的两个数的组合。处理方法是将相加问题，转为“相减”问题，即已知两个数的和为 target 及其中一个数x，求 target-x 是否存在或求它在数组中的位号。

后面两道题目都是第一题的变形。题2中，将求解问题变为了区间和，我们可以根据区间和 与前缀和的关系，将问题转换为类似求解两数和的问题。问题3 是求解两数和的问题，只是和为一组确定的值，方法也很简单，遍历这组和即可。