?本文所有題目鏈接/文章講解/視頻講解：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(n2)降到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(n2)或O(n3)優化到O(n)或O(n2)。

核心解法

1. 454. 四數相加II

解法：分組哈希 + 互補查找

• 將4數組分為2組：A+B 和 C+D

• 用map存儲A+B的所有和及其出現次數

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

• 時間復雜度：O(n2)

2. 383. 贖金信

解法：數組哈希表

• 使用長度為26的數組作為簡易哈希表

• 統計magazine中每個字母的出現次數

• 遍歷ransomNote消耗字母計數

• 關鍵點：數組比unordered_set更高效

3. 15. 三數之和

解法：排序 + 雙指針 + 去重

• 先排序以便去重和使用雙指針

• 固定一個數，轉化為兩數之和問題

• 雙指針尋找互補值，同時處理去重

• 難點：多重去重邏輯

4. 18. 四數之和

解法：雙循環 + 雙指針 + 去重

• 三數之和的擴展，多一層循環

• 固定兩個數，轉化為兩數之和問題

• 注意整數溢出和負數情況下的提前終止條件

• 關鍵點：使用long long防止溢出

?關鍵點

1. 哈希表選擇原則：

   • 需要統計次數 →?unordered_map

   • 只需要判斷存在 →?unordered_set

   • 鍵范圍小且連續 → 數組

2. 去重技巧：

   • 排序后跳過相同元素

   • 確定固定位置和移動指針

   • 在合適的位置進行去重（找到解后）

   • 注意去重條件的邊界判斷

3. 優化策略：

   • 分組處理降低復雜度

   • 雙指針替代多重循環

   • 提前終止不必要的計算（剪枝