【代码随想录】二刷-哈希表
哈希表
哈希表一般用来快速查找某个元素是否在一个集合中。
如果使用枚举的话时间复杂度为O(n)，而使用哈希表只O(1)就可以做到。——元素查询。
242.有效的字母异位词
- 使用unordered_map
// 时间复杂度 O(n) // 空间复杂度 O(n) class Solution { public: bool isAnagram(string s, string t) { unordered_map<char,int>mp; for(char& c:s)mp[c]++; for(char& c:t)mp[c]--; for(auto m:mp){ if(m.second != 0)return false; } return true; } };- 使用数组
// 时间复杂度 O(n) // 空间复杂度 O(1)-因为空间上定义的是一个常量大小的辅助数组 class Solution { public: bool isAnagram(string s, string t) { int record[26] = {0}; for(char& c:s)record[c-'a']++; for(char& c:t)record[c-'a']--; for(int i = 0 ;i < 26;i++){ if(record[i] != 0)return false; } return true; } };
349. 两个数组的交集
- unordered_set底层实现同样是哈希表，使用它可以完成去重操作。
- 因为其中的每一个元素都是唯一的。
// 时间复杂度O(n) // 空间复杂度O(n) class Solution { public: vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { unordered_set<int>nums1_count; unordered_set<int>ret; for(int& c:nums1)nums1_count.emplace(c); for(int& c:nums2){ if(nums1_count.find(c) != nums1_count.end())ret.emplace(c); } return vector<int>(ret.begin(),ret.end()); } };本体限制了用例大小，所以我们同样可以使用数组来进行哈希映射。- 如果哈希值比较少、特别分散、跨度特别大，使用数组就造成空间的极大浪费。
// 时间复杂度 O(n) // 空间复杂度 O(n) class Solution { public: vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { unordered_set<int>ret; int count[1000] = {0}; for(int &c:nums1){ count[c] = 1; } for(int &c:nums2){ if(count[c] == 1){ ret.emplace(c); } } return vector<int>(ret.begin(),ret.end()); } };
350.两个数组的交集 II
- 使用两个哈希分别保存nums1和nums2中的元素及元素个数。
- 然后选择一种一个哈希表进行遍历，看另外一个哈希表中是否有相同元素，统一元素选择出现较少的次数，然后push进结果数组ret中。
// 时间复杂度 O(n) // 空间复杂度 O(n) class Solution { public: vector<int> intersect(vector<int>& nums1, vector<int>& nums2) { unordered_map<int,int>mp1,mp2; vector<int>ret; for(int& c:nums1)mp1[c]++; for(int& c:nums2)mp2[c]++;
for(auto k:mp1){
if(k.second != 0 && mp2[k.first]){
int count = min(k.second,mp2[k.first]);
for(int i = 0;i < count;i++){
ret.emplace_back(k.first);
}
}
}
return ret;
}};
>- 使用一个哈希表来存储nums1的元素个数，然后开始遍历nums2,如果哈希表中该元素数量大于1，则--，push到ret中。
```C++
// 时间复杂度 O(n)
// 空间复杂度 O(n)
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int,int>mp;
vector<int>ret;
for(int& c:nums1){
mp[c]++;
}
for(int& c:nums2){
if(mp[c] > 0){
ret.emplace_back(c);
mp[c]--;
}
}
return ret;
}
};</code></pre>
<hr />
<h2><a href="https://leetcode.cn/problems/happy-number/">第202题. 快乐数</a></h2>
<blockquote>
<ul>
<li>题目中说了可能会死循环，所以出现已经出现过的数了，直接return false</li>
<li>用一个哈希表来保存出现过的数。
<pre><code class="language-C++">// 时间复杂度 O(logn)
// 空间复杂度 O(logn)
class Solution {
public:
int getSum(int n){
int sum = 0;
while(n){
int tmp = n%10;
sum += tmp*tmp;
n /= 10;
}
return sum;
}
bool isHappy(int n) {
unordered_set<int>st;
while(1){
int tmp =getSum(n);
if(tmp == 1){
return true;
}else{
if(st.find(tmp) != st.end()){// 找到了——出现过
return false;
}else{// 没找到
st.emplace(tmp);
}
}
n = tmp;// 更新
}
}
};</code></pre>
<hr />
<h2><a href="https://leetcode.cn/problems/two-sum/">1. 两数之和</a></h2></li>
<li>"数组中同一个元素在答案里不能重复出现。",看到这句话，就知道要使用哈希表啦。
<pre><code class="language-C++">// 时间复杂度 O(n)
// 空间复杂度 O(n)
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
// 注意: 题目说，只会存在一个有效答案。
unordered_map<int,int>map;
int n = nums.size();
for(int i = 0;i < n;i++){
auto iter = map.find(target-nums[i]);
if(iter != map.end()){// 找到了
return {iter->second,i};
}else{// 没有找到
map[nums[i]] = i;
}
}
return {};
}
};</code></pre>
<hr />
<h2><a href="https://leetcode.cn/problems/4sum-ii/">454. 四数相加 II</a></h2></li>
<li>遍历num1,num2,使用一个哈希表来存储二者元素和出现的可能及对应的次数。</li>
<li>遍历num3,num4，使用-减去其中的元素组合和，得到一个差值，并在哈希表中查询是否有这个差值，存在，将其数量累加到结果上。</li>
</ul>
</blockquote>
<pre><code class="language-C++">// 时间复杂度 O(n²)
// 空间复杂度 O(n)
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
unordered_map<int,int>mp;
int ret = 0;
for(int& a:nums1){
for(int& b:nums2){
mp[a+b]++;
}
}
for(int& c:nums3){
for(int& d:nums4){
if(mp.find(0-c-d) != mp.end()){
ret += mp[0-c-d];
}
}
}
return ret;
}
};</code></pre>
<hr />
<h2><a href="https://leetcode.cn/problems/ransom-note/">383. 赎金信</a></h2>
<blockquote>
<ul>
<li>不是所有时候都使用哈希表的，有时候使用数组可能会获得更高的效率。</li>
<li>例如本题中，我们可以得到字符出现的范围，26个字母，可卡开辟出数组的大小。</li>
<li>在本体情况下，使用map的空间消耗要比数组大一些，因为map要维护红黑树或者哈希表，而且还要做哈希函数，会更费时。
<pre><code class="language-C++">// 时间复杂度 O(n)
// 空间复杂度 O(1)-常量辅助数组
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
int record[26] = {0};
for(char &c:magazine){// 使用magazine去组成ransomNote所以先遍历它
record[c-'a']++;
}
for(char& c:ransomNote){
if(record[c-'a'] > 0){
record[c-'a']--;
}else{
return false;
}
}
return true;
}
};</code></pre></li>
<li>暴力
<pre><code class="language-C++">// 时间复杂度O(n²)
// 空间复杂度O(1)
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
int nr = ransomNote.size();
int mr = magazine.size();
for(int i = 0;i< mr;i++){
for(int j = 0;j <nr;j++){
if(magazine[i] == ransomNote[j]){//找到了一个字符
ransomNote.erase(ransomNote.begin()+j);
break;//找到了一个字符
}
}
}
return ransomNote.size() == 0;
}
};</code></pre>
<hr />
<h2><a href="https://leetcode.cn/problems/3sum/">15. 三数之和</a></h2></li>
<li>哈希表法，</li>
<li>补充: 详见下图，主要为b去重理解。
<ul>
<li>即，去除同一个元素出现3次以上引起的重复和用于优化剪枝。</li>
</ul></li>
</ul>
</blockquote>
<p><img src="https://zyximagestorage.oss-cn-beijing.aliyuncs.com/blogimages/三数之和哈希表法b去重.jpg" alt="" /></p>
<pre><code class="language-C++">// 时间复杂度 O(n²)
// 空间复杂度 O(n)
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>>ret;
int n = nums.size();
sort(nums.begin(),nums.end());// 排序是为了方便去重
// a = nums[i]
// b = nums[j]
// c = 0-a-b
for(int i = 0; i < n;i++){// a
if(nums[i] > 0){// 排完序了，第一个a还是正数，无法求和==0
break;
}
if(i > 0 && nums[i] == nums[i-1]){// a去重
continue;
}
unordered_set<int>set;
for(int j = i + 1;j < n;j++){// b
if(j > i+2 &&
nums[j] == nums[j-1] &&
nums[j-1] == nums[j-2]){// b去重
continue;
}
int c = 0-nums[i]-nums[j];// c
if(set.find(c) != set.end()){// 找到了
ret.push_back({nums[i],nums[j],c});
set.erase(c);// c去重
}else{// 没找到，将当前元素b放入
set.insert(nums[j]);
}
}
}
return ret;
}
};</code></pre>
<blockquote>
<ul>
<li>双指针:
<ul>
<li>本题目中使哈希法并不合适，因为在去重的操作中有许多细节需要注意。</li>
<li>相对于哈希法，本题使用双指针法会更高效些。</li>
</ul></li>
<li>注意:
<ul>
<li>题目中的不能重复，指的是一个组合不能重复，而组合内的三个元素是可以有重复的。</li>
<li>在遍历第一个元素时候，去重的判断,就应该为nums[i] == nums[i-1]：
<ul>
<li>若为nums[i] == nums[i+1],则为与组合内的元素对比。因为右边的第一个元素为left。</li>
</ul></li>
<li>其中一个较难点是对b,c去重的理解。详见代码中的注释。
<pre><code class="language-C++">
// 时间复杂度 O(n²)
// 空间复杂度 O(n)
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>>ret;
sort(nums.begin(),nums.end());
int n = nums.size();
for(int i = 0; i < n;i++){
if(nums[i] > 0)break;// 剪枝
if(i > 0 && nums[i] == nums[i-1]){// a去重
continue;
}
int left = i+1;
int right = n-1;
while(right > left){
int tmpSum = nums[i] + nums[left] + nums[right];
if( tmpSum > 0)right--;
else if(tmpSum < 0)left++;
else{// 找到结果了
ret.push_back(vector<int>{nums[i],nums[left],nums[right]});
// b c去重,例如: 已知两个数的和为0，知道其中的一个数，另一个数就是确定的了，所以来两个要收缩。
// 当前数与下一个数进行判断是否相同
while(right > left && nums[right] == nums[right-1])right--;
while(right > left && nums[left] == nums[left+1])left++;</code></pre></li>
</ul></li>
</ul>
</blockquote>
<pre><code> // 上面两个循环最终停在上一个元素的最后一次(前/后)出现的位置
// 当我们确定一个a之后，b+c的和就确定了；
// 进一步说，如果b+c = 5，即b=1的时候，c只能为4，
// 所以b c如果与之前相同，都要跳过，即left++/right++(如上面两个while中所示)
// 所以左右边界同时收缩，即完成去重。
// 下面收缩后，left right 都为下一个与之前计算收集结果时不同的元素。
left++;
right--;
}
}
}
return ret;
}</code></pre>
<p>};</p>
<pre><code>## [18. 四数之和](https://leetcode.cn/problems/4sum/)
>- 双指针法
```C++
// 时间复杂度 O(n³)
// 空间复杂度 O(n)
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>>ret;
int n = nums.size();
sort(nums.begin(),nums.end());
for(int i = 0; i < n ; i++){
if(nums[i] > target &&
nums[i] > 0){// 剪枝
break;
}
if(i > 0 && nums[i] == nums[i-1])continue;
for(int j = i + 1; j < n;j++){
// 注意这里判断nums[k]+nums[i] = 0，
// 如果后面还有数，当前两个相加为0，大于target，说明target为负数，后面不可能再有答案，0 + 整数 > 0
if(nums[i]+nums[j] > target &&
nums[i]+nums[j] >= 0)continue;
if(j > i + 1 && nums[j] == nums[j-1])continue;
int left = j+1;
int right = n-1;
while(right > left){
// 相加有可能溢出用long存
long tmpSum = (long)nums[i]+nums[j]+nums[left]+nums[right];
if(tmpSum > target)right--;
else if(tmpSum < target)left++;
else{
ret.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++;
left++;
right--;
}
}
}
}
return ret;
}
};