本文最后更新于 2024年8月18日 下午
视频讲解: 学透哈希表,map使用有技巧!LeetCode:454.四数相加II
文章讲解:454.四数相加
之前做过,知道用map,但是太久没用过map,一时间不知道怎么用map,干瞪眼十几分钟,最后看了题解,思路有,但是map的用法限制了我……
unordered_map怎么在算法题中使用
unordered_map是std命名空间下的,所以自己写ACM模式的时候记得加
std::
映射 |
底层实现 |
是否有序 |
数值是否可重复 |
能否更改数值 |
查询效率 |
增删效率 |
map |
红黑树 |
key有序 |
key不重复 |
key不可修改 |
O(logn) |
O(logn) |
multimap |
红黑树 |
key有序 |
key可重复 |
key不可修改 |
O(logn) |
O(logn) |
unordered_map |
哈希表 |
key无序 |
key不重复 |
key不可修改 |
O(1) |
O(1) |
由该表能看出,unordered_map查找的效率最高,但是内部元素无序
适用于:当作记录型变量用于需要多次查找的场合
创建unordered_map
1 2 3 4 5 6 7
| unordered_map<type1, type2> map;
unordered_map<t1, t2> map = {{key1, value1}, {key2, value2}, ……}; vector<pair<t1, t2>> v = {{key1, value1}, {key2, value2}, ……};
unordered_map<int, string> map(v.begin(), v.end());
|
插入一个元素进map
1 2 3 4 5 6
| map[key] = value;
map.insert(pair<type1, type2>(key, value));
map[key]++;
|
map的迭代器
1 2 3 4 5
| unordered_map<int, string> map; auto it = map.begin(); it->first = key; it->second = value;
|
map的增删改查方法
1 2 3 4
| iterator find(const type1& key) size_t count(const type1& key) insert erase
|
注意
erase
方法是使用迭代器删除元素,传入的参数指向目标的迭代器,而返回下一个元素的迭代器,用
for
遍历删除时不要 iter++
,应该使用
iter = map.erase(iter)
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| class Solution { public: int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) { unordered_map<int, int> map1; for(int a : nums1) { for(int b : nums2) { int sum = a + b; map1[sum]++; } } int ans = 0; for(int a : nums3) { for(int b : nums4) { if(map1.count(-a-b)) ans += map1[-a-b]; } } return ans; } };
|
Carl文章&视频链接:代码随想录
| 383.赎金信
看覆不覆盖就完了,用 char alpha[26]
或者开一个
map
都行,一次遍历 ++,一次遍历 --,缺了就 false,不缺就
true
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| class Solution { public: bool canConstruct(string ransomNote, string magazine) { unordered_map<int, int> map; for(char c : magazine) { map[c]++; } for(char c : ransomNote) { if(map[c]) map[c]--; else return false; } return true;
} };
|
Carl文章&视频链接:代码随想录
| 三数之和
该题看起来是两数之和的拓展,所以自然想到用双指针,但是有3个数,得3个指针,所以拆分子问题,一个指针在大循环里移动,小循环内使用两数之和的方法查找。
还得去重操作,没有关注,WA了几发,哈希做法需要大量剪枝没看。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
| class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { sort(nums.begin(), nums.end()); vector<vector<int>> ans; int n = nums.size(); for(int i = 0;i < n - 2;i++) { if(i > 0 && nums[i] == nums[i - 1]) continue; int target = -nums[i]; int left = i + 1, right = n - 1; while(left < right) { int sum = nums[left] + nums[right]; if(sum == target) { ans.push_back(vector<int>{nums[i], nums[left], nums[right]}); while(left < right && nums[left] == nums[left + 1]) left++; while(right > left && nums[right] == nums[right - 1]) right--; left++; right--; } else if(sum < target) { left++; } else right--; } } return ans; } };
|
Carl文章&视频链接:代码随想录
| 四数之和
跟三数之和差不多,继续拆分子问题套循环,不过又多了剪枝操作
还得注意范围,此题会爆 int
,得用
long long
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
| class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { sort(nums.begin(), nums.end()); vector<vector<int>> ans; int n = nums.size(); for(int i = 0;i < n - 3;i++) { if(i > 0 && nums[i] == nums[i - 1]) continue; if ((long long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) { break; } if ((long long) nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) { continue; } for(int j = i + 1;j < n - 2;j++) { if(j > i + 1 && nums[j] == nums[j - 1]) continue; if ((long long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) { break; } if ((long long) nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target) { continue; } int left = j + 1, right = n - 1; while(left < right) { long long sum = (long long)nums[left] + nums[right] + nums[i] + nums[j]; if(sum == target) { ans.push_back(vector<int> {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--; } else if(sum > target) { right--; } else left++; } } } return ans; } };
|