本文所有题目链接/文章讲解/视频讲解：https://programmercarl.com/0454.%E5%9B%9B%E6%95%B0%E7%9B%B8%E5%8A%A0II.html

454.四数相加II

有四个数组，如果要遍历则时间复杂度太大
可以选择分组，a和b一组，c和d一组
这样就可以等同于两个数之和为0的情况了
只需要把a+b的所有可能和放入哈希表，然后c和d的和再找哈希表里能和它们加和等于0的
哈希表使用map，一个表示ab的和，一个表示次数

class Solution {
public:int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {//有四个数组，如果要遍历则时间复杂度太大//则可以选择分组，a和b一组，c和d一组//这样就可以等同于两个数之和为0的情况了//只需要把a+b的所有可能和放入哈希表，然后c和d的和再找哈希表里能和它们加和等于0的//哈希表使用map，一个表示ab的和，一个表示次数unordered_map<int,int> m;for(int i=0;i<nums1.size();i++){for(int j=0;j<nums2.size();j++){m[nums1[i]+nums2[j]]++;}}int count=0;for(int i=0;i<nums3.size();i++){for(int j=0;j<nums4.size();j++){int s=-(nums3[i]+nums4[j]);if(m.find(s)!=m.end()){count+=m[s];}}}return count;}
};

383. 赎金信

本题和 242.有效的字母异位词是同样类型的题目，思路都是一样的，使用数组做哈希表

class Solution {
public:bool canConstruct(string ransomNote, string magazine) {//把magazine里的字母存入哈希表//再进行比对，如果有则对应数量-1，如果没有则返回false//最终返回trueint s[26]={0};for(int i=0;i<magazine.size();i++){s[magazine[i]-'a']++;}for(int i=0;i<ransomNote.size();i++){if(s[ransomNote[i]-'a']==0){return false;}s[ransomNote[i]-'a']--;}return true;}
};

15. 三数之和

这题的主要难点在于如何去重，这题应该用双指针，而不是哈希（哈希也可做，但是会比较麻烦

排序+双指针（最优解）：

先对数组排序（O(n log n)）

固定一个数 nums[i]，然后使用双指针在剩余数组中寻找两个数

排序后可以方便地去重

双指针可以将两数之和的时间复杂度从O(n²)降到O(n)

双指针也需要去重，只是由于排序过，略微简单了一点，下面记录去重的思路：
   1. 由于去重指的是不同的结果集不能有重复的三元组
   2. 其中i指针指向a，是固定的，再去找符合条件的b和c，则固定数去重的思路是判断nums[i]是否与上一位也就是nums[i-1]相同。这样可以避免产生重复的三元组
   3. 接着是找到解之和的去重：
找到解之和，我们去看后面有无与b、c重复的元素，对于b来说是后面的元素（直到找到与当前位置不一样的数），对于c是前面的元素（直到找到与当前位置不一样的数）

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;if(i>0 && nums[i]==nums[i-1])continue;int left=i+1;int right=nums.size()-1;while(left < right){//遍历寻找if(nums[i]+nums[right]+nums[left]>0) {right--;}else if(nums[i]+nums[right]+nums[left]<0){left++;}else{result.push_back(vector<int>{nums[i], nums[left], nums[right]});//去重while(right > left && nums[left]==nums[left+1]){left++;}//为什么是nums[left]=nums[left+1]???while(right > left && nums[right]==nums[right-1]){right--;}left++;right--;}}}return result;}
};

18. 四数之和

这题和上一题思路一样，就是多加了一层循环

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {//和三数之和类似的思路//先固定a和b的下标，再去找c和dvector<vector<int>> result;sort(nums.begin(),nums.end());for(int i=0;i<nums.size();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();j++){if(nums[j] + nums[i] > target && nums[j] + nums[i] >= 0) break;//当target是负数时，只有nums[j] + nums[i] > targe这一个条件，不行，因为后面可能还有负数，所以要确保是正数if(j > i + 1 && nums[j]==nums[j-1]) continue;int left=j+1;int right=nums.size()-1;long long sum=(long long)target-(nums[i]+nums[j]);while(left<right){if((long long)nums[left]+nums[right]>sum){right--;}else if((long long)nums[left]+nums[right]<sum){left++;}else{result.push_back(vector<int>{nums[i],nums[j],nums[left],nums[right]});while(left<right && nums[right]==nums[right-1]){right--;}while(left<right && nums[left]==nums[left+1]){left++;}right--;left++;}}}}return result;}
};

总结

总体思路

本专题主要围绕哈希表的应用展开，涵盖了数组、set、map三种哈希表实现方式，解决了多种求和、计数、去重问题。核心思想是用空间换时间，将时间复杂度从O(n²)或O(n³)优化到O(n)或O(n²)。

核心解法

1. 454. 四数相加II

解法：分组哈希 + 互补查找

将4数组分为2组：A+B 和 C+D

用map存储A+B的所有和及其出现次数

查找C+D的和的相反数是否在map中

时间复杂度：O(n²)

2. 383. 赎金信

解法：数组哈希表

使用长度为26的数组作为简易哈希表

统计magazine中每个字母的出现次数

遍历ransomNote消耗字母计数

关键点：数组比unordered_set更高效

3. 15. 三数之和

解法：排序 + 双指针 + 去重

先排序以便去重和使用双指针

固定一个数，转化为两数之和问题

双指针寻找互补值，同时处理去重

难点：多重去重逻辑

4. 18. 四数之和

解法：双循环 + 双指针 + 去重

三数之和的扩展，多一层循环

固定两个数，转化为两数之和问题

注意整数溢出和负数情况下的提前终止条件

关键点：使用long long防止溢出

关键点

哈希表选择原则：
- 需要统计次数 → unordered_map
- 只需要判断存在 → unordered_set
- 键范围小且连续 → 数组
去重技巧：
- 排序后跳过相同元素
- 确定固定位置和移动指针
- 在合适的位置进行去重（找到解后）
- 注意去重条件的边界判断
优化策略：
- 分组处理降低复杂度
- 双指针替代多重循环
- 提前终止不必要的计算（剪枝