哈希与双指针算法实战：LeetCode经典题目解析

1. 算法训练营第七天哈希与双指针实战解析今天我们将深入探讨LeetCode中四道经典题目454.四数相加II、383.赎金信、15.三数之和和18.四数之和。这些题目涵盖了哈希表和双指针两大核心算法技巧是面试中高频出现的题型。我将结合自己刷题300的经验分享这些题目的解题思路、代码实现和易错点。2. 454. 四数相加II2.1 问题分析与解法选择给定四个整数数组nums1、nums2、nums3和nums4计算有多少个元组(i,j,k,l)满足nums1[i] nums2[j] nums3[k] nums4[l] 0。题目要求我们统计满足条件的四元组数量而不是返回具体的组合。这道题的暴力解法是四重循环时间复杂度为O(n^4)显然不可取。更优的解法是将问题分解为两个部分先计算nums1和nums2中所有可能的和并统计每个和出现的次数然后计算nums3和nums4中所有可能的和查找其相反数在第一步结果中出现的次数这种分组哈希表的方法将时间复杂度降低到O(n^2)是典型的空间换时间策略。2.2 代码实现与细节处理class Solution { public: int fourSumCount(vectorint nums1, vectorint nums2, vectorint nums3, vectorint nums4) { unordered_mapint, int sumAB; // 存储AB的和及其出现次数 int count 0; // 计算所有AB的可能和 for (int a : nums1) { for (int b : nums2) { sumAB[a b]; } } // 计算所有CD的可能和并查找-(cd)是否在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)最坏情况下AB的所有和都不相同实际编码中有几个注意点使用unordered_map而不是map因为前者查询效率更高在统计count时直接累加哈希表中的值而不是每次1变量命名要有意义如sumAB比hashmap更能表达意图3. 383. 赎金信3.1 问题理解与解法思路给定两个字符串ransomNote和magazine判断ransomNote是否能由magazine中的字符构成。magazine中的每个字符只能在ransomNote中使用一次。这道题与242.有效的字母异位词类似都是统计字符出现次数的题目。我们可以使用长度为26的数组来记录每个字母的出现次数先遍历magazine统计每个字母出现的次数再遍历ransomNote减少对应字母的计数如果在减少过程中任何字母的计数变为负数则返回false3.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。这道题的难点在于需要找到所有可能的组合而不仅仅是判断是否存在结果中不能包含重复的三元组最优解法需要低于O(n^3)的时间复杂度双指针法是解决这类问题的标准方法基本思路是先对数组排序固定一个数nums[i]然后在剩余部分使用双指针寻找两数之和等于-nums[i]通过跳过重复元素来避免重复解4.2 代码实现与关键细节class Solution { public: vectorvectorint threeSum(vectorint nums) { vectorvectorint 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[left1]) left; while (left right nums[right] nums[right-1]) right--; left; right--; } } } return result; } };4.3 常见错误与注意事项忘记排序数组导致双指针法无法工作去重逻辑处理不当可能漏解或产生重复解边界条件处理如数组长度小于3的情况整数溢出问题特别是当target不是0时5. 18. 四数之和5.1 问题扩展与解法演进四数之和是三数之和的扩展给定一个数组和一个target值找出所有不重复的四元组[a,b,c,d]使得a b c d target。解法思路是在三数之和的基础上再加一层循环先对数组排序固定两个数nums[i]和nums[j]然后在剩余部分使用双指针寻找两数之和等于target-nums[i]-nums[j]添加适当的剪枝条件和去重逻辑5.2 代码实现与剪枝优化class Solution { public: vectorvectorint fourSum(vectorint nums, int target) { vectorvectorint 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[left1]) left; while (left right nums[right] nums[right-1]) right--; left; right--; } } } } return result; } };5.3 关键差异与注意事项与三数之和相比四数之和有几个关键差异点剪枝条件更复杂不能简单判断nums[i]target就终止需要处理整数溢出问题特别是当target很大时去重逻辑需要处理两层循环时间复杂度上升到O(n^3)对于大n可能不够高效在实际编码中我发现最容易出错的地方是剪枝条件的处理。例如当target为负数时即使nums[i]target也不能直接剪枝因为后面的负数相加可能达到target。6. 总结与刷题建议通过这四道题目我们系统性地学习了哈希表和双指针在求和类问题中的应用。在实际刷题过程中我有以下几点建议对于哈希表问题要清楚知道为什么选择哈希表以及如何设计键和值双指针问题通常需要先排序要熟练掌握各种去重技巧注意边界条件和特殊测试用例如空数组、全零数组等对于n数之和这类问题要理解从两数之和到n数之和的演进规律在面试中遇到类似问题时建议先明确问题要求是否需要所有解、是否允许重复等然后分析时间复杂度和空间复杂度最后再开始编码。记得在编码过程中添加适当的注释解释关键步骤的意图。