【代码随想录】二刷-哈希表

9

哈希表

  • 《代码随想录》

  • 哈希表一般用来快速查找某个元素是否在一个集合中。

  • 如果使用枚举的话时间复杂度为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-&#039;a&#039;]++;
}
for(char& c:ransomNote){
if(record[c-&#039;a&#039;] > 0){
record[c-&#039;a&#039;]--;
}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;
    }
};