哈希表

map set 數組

在C++中，set 和 map 分別提供以下三種數據結構，其底層實現以及優劣如下表所示：

集合	底層實現	是否有序	數值是否可以重復	能否更改數值	查詢效率	增刪效率
std::set	紅黑樹	有序	否	否	O(log n)	O(log n)
std::multiset	紅黑樹	有序	是	否	O(logn)	O(logn)
std::unordered_set	哈希表	無序	否	否	O(1)	O(1)

std::unordered_set底層實現為哈希表，std::set 和std::multiset 的底層實現是紅黑樹，

紅黑樹是一種平衡二叉搜索樹，所以key值是有序的，但key不可以修改，改動key值會導致整棵樹的錯亂，所以只能刪除和增加。

映射	底層實現	是否有序	數值是否可以重復	能否更改數值	查詢效率	增刪效率
std::map	紅黑樹	key有序	key不可重復	key不可修改	O(logn)	O(logn)
std::multimap	紅黑樹	key有序	key可重復	key不可修改	O(log n)	O(log n)
std::unordered_map	哈希表	key無序	key不可重復	key不可修改	O(1)	O(1)

std::unordered_map 底層實現為哈希表，std::map 和std::multimap 的底層實現是紅黑樹。

同理，std::map 和std::multimap 的key也是有序的

Set與Multiset-筆記-CSDN博客

有效的字母異位詞

思路

定義一個數組叫做record用來上記錄字符串s里字符出現的次數

242. 有效的字母異位詞 - 力扣（LeetCode）

兩個數組的交集

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {unordered_set<int>result_set;unordered_set<int>nums_set(nums1.begin(),nums1.end());for(auto n2:nums2){if(nums_set.find(n2)!=nums_set.end()){result_set.insert(n2);}}return vector<int>(result_set.begin(),result_set.end());}
};

兩數之和

在遍歷數組的時候，只需要向map去查詢是否有和目前遍歷元素匹配的數值，如果有，就找到的匹配對，如果沒有，就把目前遍歷的元素放進map中，因為map存放的就是我們訪問過的元素

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {std::unordered_map <int,int> map;for(int i = 0; i < nums.size(); i++) {// 遍歷當前元素，并在map中尋找是否有匹配的keyauto iter = map.find(target - nums[i]); if(iter != map.end()) {return {iter->second, i};}// 如果沒找到匹配對，就把訪問過的元素和下標加入到map中map.insert(pair<int, int>(nums[i], i)); }return {};}
};

1. 兩數之和 - 力扣（LeetCode）

四數之和

1. 遍歷大A和大B數組，統計兩個數組元素之和，和出現的次數，放到map中。
2. 1. 再遍歷大C和大D數組，找到如果 0-(c+d) 在map中出現過的話，就用count把map中key對應的value也就是出現次數統計出來。

三數之和

雙指針
依然還是在數組中找到 abc 使得a + b +c =0，我們這里相當于 a = nums[i]，b = nums[left]，c = nums[right]。

如果nums[i] + nums[left] + nums[right] > 0
說明 此時三數之和大了，因為數組是排序后了，所以right下標就應該向左移動，這樣才能讓三數之和小一些。

如果 nums[i] + nums[left] + nums[right] < 0
說明 此時 三數之和小了，left 就向右移動，才能讓三數之和大一些，直到left與right相遇為止