LeetCode 383. 赎金信：哈希表与数组计数法对比

LeetCode 383. 赎金信

给你两个字符串：ransomNote 和 magazine，判断 ransomNote 能不能由 magazine 中的字符构成。

如果可以，返回 true；否则返回 false。

magazine 中的每个字符只能在 ransomNote 中使用一次。

提示：

• 1 <= ransomNote.length, magazine.length <= 10⁵
• ransomNote 和 magazine 由小写英文字母组成

---

方案一：哈希表统计

解题思路

核心方法：哈希表统计 + 逐字符校验。先统计 ransomNote 中每个字符的需求数量，再遍历 magazine 逐个扣减计数。逻辑直观但嵌套遍历导致性能低效。

核心逻辑拆解

判断赎金信能否构造的核心是'字符数量匹配'：

1. 边界预判：若 magazine 长度小于 ransomNote，直接返回 false（字符数量不够，无法构造）；
2. 统计需求：用 HashMap 统计 ransomNote 中每个字符需要的数量（比如 ransomNote="aa"，则 map 中 a:2）；
3. 校验供给：遍历 HashMap 中的每个字符，再遍历 magazine 统计该字符的出现次数，扣减需求数量；
4. 结果判断：若某字符扣减后仍有剩余需求（count>0），返回 false；全部字符满足则返回 true。

复杂度分析

• 时间复杂度：O(m×n)（m 为 ransomNote 的不同字符数，n 为 magazine 长度），最坏情况需遍历 magazine 多次；
• 空间复杂度：O(k)（k 为 ransomNote 的不同字符数，最多 26）；
• 核心损耗点：嵌套遍历导致重复扫描，HashMap 的增删查操作及自动装箱/拆箱增加额外开销。

public boolean canConstruct(String ransomNote, String magazine) {
    if (magazine.length() < ransomNote.length()) {
        return false;
    }
    Map<Character, Integer> map = new HashMap<>();
    for (int i = 0; i < ransomNote.length(); i++) {
           ransomNote.charAt(i);
         (map.containsKey(a)) {
            map.put(a, map.get(a) + );
        }  {
            map.put(a, );
        }
    }
       ;
     ( key : map.keySet()) {
           map.get(key);
         (   ; i < magazine.length(); i++) {
             (magazine.charAt(i) == key) {
                count--;
            }
        }
         (count > ) {
            result = ;
            ;
        }
    }
     result;
}