哈希表与双指针法解决数组求和问题

1. 四数相加 II问题解析1.1 问题理解与思路分析四数相加II问题要求我们统计四个数组中满足abcd0的元组数量。直接暴力解法需要O(n⁴)的时间复杂度显然不可取。更聪明的做法是将问题拆分为两个部分先计算A和B数组中所有可能的ab组合用哈希表记录每种和出现的次数然后计算C和D数组中所有可能的cd组合查找哈希表中是否存在-(cd)这种分治策略将时间复杂度从O(n⁴)降低到O(n²)是典型的空间换时间优化。1.2 代码实现细节class Solution { public: int fourSumCount(vectorint nums1, vectorint nums2, vectorint nums3, vectorint nums4) { unordered_mapint,int map; int count0; // 计算AB的所有组合 for(int a:nums1){ for(int b:nums2){ map[ab]; } } // 计算CD的所有组合并查找匹配 for(int c:nums3){ for(int d:nums4){ int target0-(cd); if(map.find(target)!map.end()){ countmap[target]; } } } return count; } };注意这里使用unordered_map而不是map因为前者基于哈希表实现查找时间复杂度为O(1)而后者基于红黑树实现查找时间复杂度为O(logn)。1.3 复杂度分析与优化时间复杂度O(n²)因为有两层嵌套循环每层遍历n个元素空间复杂度O(n²)最坏情况下AB的所有组合都不相同实际应用中如果内存是瓶颈可以考虑分批处理先将AB的结果存入哈希表然后处理部分CD组合后清除部分哈希表条目但这会增加时间复杂度。2. 赎金信问题解析2.1 问题理解与思路分析赎金信问题要求判断ransomNote字符串是否能由magazine字符串中的字符组成。核心要点magazine中的每个字符只能使用一次ransomNote必须完全由magazine中的字符组成大小写敏感本题中都是小写2.2 代码实现与优化class Solution { public: bool canConstruct(string ransomNote, string magazine) { vectorint record(26,0); // 快速失败如果ransomNote比magazine长直接返回false if(ransomNote.size()magazine.size()){ return false; } // 统计magazine中各字符出现次数 for(int i0;imagazine.size();i){ record[magazine[i]-a]; } // 检查ransomNote中的字符是否都能满足 for(int i0;iransomNote.size();i){ record[ransomNote[i]-a]--; if(record[ransomNote[i]-a]0){ return false; } } return true; } };2.3 复杂度分析与变种时间复杂度O(mn)其中m和n分别是magazine和ransomNote的长度空间复杂度O(1)因为只使用了固定大小的数组26个字母如果字符集更大如包含Unicode字符可以使用unordered_map代替固定数组但会增加一些常数时间开销。3. 三数之和问题解析3.1 问题理解与思路分析三数之和问题要求在数组中找到所有不重复的三元组使得它们的和为0。这个问题的难点在于需要避免重复的三元组需要高效地找到所有可能的组合哈希表解法虽然可行但去重逻辑较为复杂。更推荐使用双指针法先对数组排序固定一个数nums[i]然后在剩余部分使用双指针寻找nums[left]nums[right]-nums[i]通过跳过重复元素来避免重复解3.2 哈希表解法代码class Solution { public: vectorvectorint threeSum(vectorint nums) { sort(nums.begin(),nums.end()); vectorvectorint result; for(int a0;anums.size();a){ // 跳过重复的a if(a0nums[a]nums[a-1]){ continue; } unordered_setint set; for(int ka1;knums.size();k){ // 复杂的去重逻辑 if(ka2nums[k]nums[k-1]nums[k-1]nums[k-2]){ continue; } int target0-(nums[a]nums[k]); if(set.find(target)!set.end()){ result.push_back({nums[a],target,nums[k]}); set.erase(target); // 防止重复解 } else{ set.insert(nums[k]); } } } return result; } };3.3 双指针解法推荐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; // 优化第一个数大于0后面不可能有解 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. 四数之和问题解析4.1 问题理解与思路分析四数之和是三数之和的扩展要求在数组中找到所有不重复的四元组使得它们的和等于目标值。解题思路先对数组排序固定两个数nums[i]和nums[j]然后在剩余部分使用双指针寻找nums[left]nums[right]target-nums[i]-nums[j]通过跳过重复元素来避免重复解4.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 (i 0 nums[i] nums[i - 1]) continue; // 去重 for (int j i 1; j nums.size() - 2; j) { 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 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; } };4.3 复杂度分析与优化时间复杂度O(n³)外层两层循环内层双指针空间复杂度O(1)或O(n)取决于排序算法优化点提前终止如果nums[i]nums[i1]nums[i2]nums[i3] target可以提前终止跳过不可能的组合如果nums[i]nums[n-3]nums[n-2]nums[n-1] target可以跳过当前i5. 总结与对比5.1 四种问题的异同点问题类型解法核心时间复杂度空间复杂度关键难点四数相加II哈希表分治O(n²)O(n²)将四数问题拆分为两个两数问题赎金信字符统计O(mn)O(1)字符频率统计与比较三数之和排序双指针O(n²)O(1)或O(n)去重处理四数之和排序双指针O(n³)O(1)或O(n)双重去重处理5.2 解题技巧总结哈希表是处理查找互补元素类问题的高效工具对于需要去重的问题排序往往是必要的第一步双指针法在有序数组中可以有效降低时间复杂度分治思想如将四数问题拆分为两数问题可以显著提高效率提前终止和跳过不可能的组合是常见的优化手段在实际编程面试中理解这些问题的本质和掌握多种解法非常重要。特别是三数之和和四数之和问题它们考察的不仅是编码能力还有对算法优化的理解和实现细节的把控。