1. 算法训练营第七天：哈希与双指针实战解析

今天我们将深入探讨LeetCode中四道经典题目：454.四数相加II、383.赎金信、15.三数之和和18.四数之和。这些题目涵盖了哈希表和双指针两大核心算法技巧，是面试中高频出现的题型。我将结合自己刷题300+的经验，分享这些题目的解题思路、代码实现和易错点。

2. 454. 四数相加II

2.1 问题分析与解法选择

给定四个整数数组nums1、nums2、nums3和nums4，计算有多少个元组(i,j,k,l)满足nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0。题目要求我们统计满足条件的四元组数量，而不是返回具体的组合。

这道题的暴力解法是四重循环，时间复杂度为O(n^4)，显然不可取。更优的解法是将问题分解为两个部分：

1. 先计算nums1和nums2中所有可能的和，并统计每个和出现的次数
2. 然后计算nums3和nums4中所有可能的和，查找其相反数在第一步结果中出现的次数

这种分组+哈希表的方法将时间复杂度降低到O(n^2)，是典型的空间换时间策略。

2.2 代码实现与细节处理

class Solution { public: int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) { unordered_map<int, int> sumAB; // 存储A+B的和及其出现次数 int count = 0; // 计算所有A+B的可能和 for (int a : nums1) { for (int b : nums2) { sumAB[a + b]++; } } // 计算所有C+D的可能和，并查找-(c+d)是否在sumAB中 for (int c : nums3) { for (int d : nums4) { int target = -(c + d); if (sumAB.find(target) != sumAB.end()) { count += sumAB[target]; } } } return count; } };

2.3 复杂度分析与优化空间

• 时间复杂度：O(n^2)，我们进行了两次双重循环
• 空间复杂度：O(n^2)，最坏情况下A+B的所有和都不相同

实际编码中有几个注意点：

1. 使用unordered_map而不是map，因为前者查询效率更高
2. 在统计count时直接累加哈希表中的值，而不是每次+1
3. 变量命名要有意义，如sumAB比hashmap更能表达意图

3. 383. 赎金信

3.1 问题理解与解法思路

给定两个字符串ransomNote和magazine，判断ransomNote是否能由magazine中的字符构成。magazine中的每个字符只能在ransomNote中使用一次。

这道题与242.有效的字母异位词类似，都是统计字符出现次数的题目。我们可以使用长度为26的数组来记录每个字母的出现次数：

1. 先遍历magazine，统计每个字母出现的次数
2. 再遍历ransomNote，减少对应字母的计数
3. 如果在减少过程中任何字母的计数变为负数，则返回false

3.2 代码实现与边界处理

class Solution { public: bool canConstruct(string ransomNote, string magazine) { if (ransomNote.size() > magazine.size()) { return false; } int count[26] = {0}; // 统计magazine中的字母 for (char c : magazine) { count[c - 'a']++; } // 检查ransomNote中的字母 for (char c : ransomNote) { count[c - 'a']--; if (count[c - 'a'] < 0) { return false; } } return true; } };

3.3 优化与变种思考

• 提前判断ransomNote长度是否大于magazine，可以快速返回false
• 如果字符集更大（如包含Unicode），可以使用unordered_map代替数组
• 实际面试中可能会被问到如何优化空间，可以只统计ransomNote需要的字符

4. 15. 三数之和

4.1 问题特点与解法选择

给定一个整数数组nums，找出所有不重复的三元组[a,b,c]，使得a + b + c = 0。这道题的难点在于：

1. 需要找到所有可能的组合，而不仅仅是判断是否存在
2. 结果中不能包含重复的三元组
3. 最优解法需要低于O(n^3)的时间复杂度

双指针法是解决这类问题的标准方法，基本思路是：

1. 先对数组排序
2. 固定一个数nums[i]，然后在剩余部分使用双指针寻找两数之和等于-nums[i]
3. 通过跳过重复元素来避免重复解

4.2 代码实现与关键细节

class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> result; sort(nums.begin(), nums.end()); for (int i = 0; i < nums.size(); i++) { // 提前终止条件 if (nums[i] > 0) break; // 跳过重复的nums[i] if (i > 0 && nums[i] == nums[i-1]) continue; int left = i + 1, right = nums.size() - 1; while (left < right) { int sum = nums[i] + nums[left] + nums[right]; if (sum < 0) { left++; } else if (sum > 0) { right--; } else { result.push_back({nums[i], nums[left], nums[right]}); // 跳过重复元素 while (left < right && nums[left] == nums[left+1]) left++; while (left < right && nums[right] == nums[right-1]) right--; left++; right--; } } } return result; } };

4.3 常见错误与注意事项

1. 忘记排序数组，导致双指针法无法工作
2. 去重逻辑处理不当，可能漏解或产生重复解
3. 边界条件处理，如数组长度小于3的情况
4. 整数溢出问题，特别是当target不是0时

5. 18. 四数之和

5.1 问题扩展与解法演进

四数之和是三数之和的扩展，给定一个数组和一个target值，找出所有不重复的四元组[a,b,c,d]，使得a + b + c + d = target。

解法思路是在三数之和的基础上再加一层循环：

1. 先对数组排序
2. 固定两个数nums[i]和nums[j]，然后在剩余部分使用双指针寻找两数之和等于target-nums[i]-nums[j]
3. 添加适当的剪枝条件和去重逻辑

5.2 代码实现与剪枝优化

class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { vector<vector<int>> result; if (nums.size() < 4) return result; sort(nums.begin(), nums.end()); for (int i = 0; i < nums.size() - 3; i++) { // 一级剪枝 if (nums[i] > target && nums[i] >= 0) break; // 去重 if (i > 0 && nums[i] == nums[i-1]) continue; for (int j = i + 1; j < nums.size() - 2; j++) { // 二级剪枝 if (nums[i] + nums[j] > target && nums[j] >= 0) break; // 去重 if (j > i + 1 && nums[j] == nums[j-1]) continue; int left = j + 1, right = nums.size() - 1; while (left < right) { // 使用long防止溢出 long sum = (long)nums[i] + nums[j] + nums[left] + nums[right]; if (sum < target) { left++; } else if (sum > target) { right--; } else { result.push_back({nums[i], nums[j], nums[left], nums[right]}); // 跳过重复元素 while (left < right && nums[left] == nums[left+1]) left++; while (left < right && nums[right] == nums[right-1]) right--; left++; right--; } } } } return result; } };

5.3 关键差异与注意事项

与三数之和相比，四数之和有几个关键差异点：

1. 剪枝条件更复杂，不能简单判断nums[i]>target就终止
2. 需要处理整数溢出问题，特别是当target很大时
3. 去重逻辑需要处理两层循环
4. 时间复杂度上升到O(n^3)，对于大n可能不够高效

在实际编码中，我发现最容易出错的地方是剪枝条件的处理。例如，当target为负数时，即使nums[i]>target，也不能直接剪枝，因为后面的负数相加可能达到target。

6. 总结与刷题建议

通过这四道题目，我们系统性地学习了哈希表和双指针在求和类问题中的应用。在实际刷题过程中，我有以下几点建议：

1. 对于哈希表问题，要清楚知道为什么选择哈希表，以及如何设计键和值
2. 双指针问题通常需要先排序，要熟练掌握各种去重技巧
3. 注意边界条件和特殊测试用例，如空数组、全零数组等
4. 对于n数之和这类问题，要理解从两数之和到n数之和的演进规律

在面试中遇到类似问题时，建议先明确问题要求（是否需要所有解、是否允许重复等），然后分析时间复杂度和空间复杂度，最后再开始编码。记得在编码过程中添加适当的注释，解释关键步骤的意图。