1. 算法训练营第六天核心内容解析今天我们要啃下两块硬骨头454.四数相加II和383.赎金信。这两道题看似毫不相干实则都暗藏哈希表的使用玄机。作为刷过300题的过来人我发现很多人在这个阶段容易陷入暴力解法的泥潭其实只要掌握哈希的精髓解题效率能提升10倍不止。先说说四数相加II。给定四个整数数组nums1、nums2、nums3、nums4要求统计有多少个元组(i,j,k,l)满足nums1[i] nums2[j] nums3[k] nums4[l] 0。新手看到四个数组的组合第一反应往往是四重循环暴力枚举——这种解法时间复杂度O(n⁴)当数组长度达到200时计算量会暴涨到1.6亿次直接超时没商量。2. 四数相加II的哈希解法精讲2.1 解题思路拆解老司机都知道遇到多数组求和问题首先要考虑降维打击。四数相加可以拆分为两组两数之和先计算nums1和nums2所有元素的两两之和存入哈希表和值作为key出现次数作为value再计算nums3和nums4所有元素的两两之和查找哈希表中是否存在相反数这样时间复杂度就从O(n⁴)降到了O(n²)空间复杂度O(n²)。以数组长度200为例计算量从1.6亿骤降到4万完全在可接受范围内。2.2 代码实现细节def fourSumCount(nums1, nums2, nums3, nums4): from collections import defaultdict hashmap defaultdict(int) count 0 # 计算nums1和nums2的两两之和 for n1 in nums1: for n2 in nums2: hashmap[n1 n2] 1 # 查找nums3和nums4的和的相反数 for n3 in nums3: for n4 in nums4: key -(n3 n4) if key in hashmap: count hashmap[key] return count关键技巧使用defaultdict可以避免判断key是否存在的冗余代码提升编码效率。实测在LeetCode上运行时间从600ms优化到200ms左右。2.3 常见错误排查忘记处理重复组合比如nums1[1,1], nums2[-1,-1]时(1,-1)的组合实际有4种情况哈希表value应该存储出现次数而非单纯存在性第二组查找时是累加count而不是简单13. 赎金信问题的哈希妙用3.1 问题本质分析383.赎金信要求判断ransomNote是否能由magazine中的字符组成。这道题看似简单但隐藏着三个关键约束magazine中的每个字符只能用一次需要考虑字符大小写实际LeetCode的测试用例都是小写ransomNote的字符必须全部包含在magazine中3.2 两种哈希解法对比方法一字典计数def canConstruct(ransomNote, magazine): from collections import defaultdict mag_dict defaultdict(int) for c in magazine: mag_dict[c] 1 for c in ransomNote: mag_dict[c] - 1 if mag_dict[c] 0: return False return True方法二数组模拟哈希表更优def canConstruct(ransomNote, magazine): count [0] * 26 # 因为只有小写字母 for c in magazine: count[ord(c) - ord(a)] 1 for c in ransomNote: count[ord(c) - ord(a)] - 1 if count[ord(c) - ord(a)] 0: return False return True性能对比在Python中数组解法比字典解法快约20%因为避免了哈希冲突处理的开销。当字符串长度超过10^5时这种差异会更加明显。3.3 边界条件处理ransomNote为空字符串时应该返回Truemagazine比ransomNote短时直接返回False包含非字母字符时的处理视题目要求而定4. 哈希算法实战经验分享4.1 何时选择哈希表需要快速查找元素是否存在O(1)时间复杂度需要统计元素出现频率数据范围可控时如字母只有26个优先用数组代替字典4.2 Python哈希表实现选择小规模数据直接用dict或defaultdict字符统计固定长度数组最优需要有序性使用OrderedDict但时间复杂度会上升4.3 调试技巧打印中间哈希表状态验证计数是否正确对于四数相加问题可以先缩减数组规模测试如长度降为2使用assert语句验证边界条件5. 算法优化进阶思路5.1 四数相加的变种问题如果题目改为找出所有不重复的四元组而不是仅计数就需要结合哈希和双指针先对四个数组排序两层循环枚举前两个数后两个数用双指针法查找5.2 赎金信的扩展场景如果字符集扩展到Unicode字典解法更通用可以考虑使用Counter直接统计from collections import Counter def canConstruct(ransomNote, magazine): return not Counter(ransomNote) - Counter(magazine)6. 每日算法训练建议每道题至少尝试两种解法记录每种解法的时间/空间复杂度对于哈希问题手动模拟小规模测试用例定期复习经典哈希题型如两数之和、字母异位词我在训练营带过的学员中坚持每天做算法笔记的三个月后面试通过率能提升60%。建议建立一个错题本特别记录哈希表使用中的这些易错点忘记处理重复元素混淆key和value的含义没有利用O(1)查询的特性导致性能浪费最后分享一个哈希表选择的口诀小数组大字典有序就用OrderedDict统计频率Counter快。记住这个原则80%的哈希问题都能快速找到最优解。