DDL's homepage

哈希专题

发表于 Valine：

用哈希表(hash table) 常见的场景是用空间换时间

  1. 如果求解决方案或者数量，存的一般就是XXX->数量的映射，eg.560.

  2. 如果求的是最长最短等性质 一般存的就是XXX->下标的映射 525.连续数组

总结

560. 和为K的子数组

原题链接

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数

一开始拿到这个题目,想到通过双指针找连续子序列和的方法来做,但是这个题目还是不一样的.
但是之前的题目是

输入一个正数s，打印出所有和为s的连续正数序列（至少含有两个数）。
例如输入15，由于1+2+3+4+5=4+5+6=7+8=15，所以结果打印出3个连续序列1～5、4～6和7～8。

这里有明显的单调性,当移动 i 时,如果此时sum>k,那么就只能够向右移动j,所以我们才能够用双指针来做!!!

一个感悟:题目做多了容易将很多细微的差别搞混了,同时也很容易乱用方法,没有别的办法,多总结.

首先看一下暴力做法
两重循环,预处理一下前缀和

为什么能优化，起始这个最开始的想法来自于lc2.sum2 通过hash 空间换时间 来查找之前出现元素的个数

今天学习了一个更加巧妙的方法 前缀和+哈希

具体思路:
我们很熟悉了 如何去求一段区间和 [l,r]=s[r]-s[l-1]

我们现在需要求的是和为k的区间个数cnt,如果我们将右区间和sum固定 那么cnt==sum-k的个数

通过哈希表来存储这样一个键值对{前缀和,出现次数个数}

1
2
3
4
5
6
7
8
9
10
11
12
int subarraySum(vector<int>& nums, int k) {
        unordered_map<int,int > map;
        map[0]=1;//初始前缀和等于0的子串个数为1
        int sum=0,res=0;
        for(auto c:nums){
            sum+=c;
            res+=map[sum-k];
            map[sum]++;
        }
        return res;

    }

594. 最长和谐子序列

和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是1。

现在，给定一个整数数组，你需要在所有可能的子序列中找到最长的和谐子序列的长度。

解法1.两次扫描

思路:

  • hash 统计每个数字出现次数
  • 如果 num+1 在哈希中, 取max(res,hash[num]+hash[num+1])
1
2
3
4
5
6
7
8
9
int findLHS(vector<int>& nums) {
        unordered_map<int,int> hash;
        int res=0;
        for(auto c:nums) hash[c]++;
        for(auto c:nums){
            if(hash.count(c+1)) res=max(res,hash[c]+hash[c+1]);
        }
        return res;
    }

解法2. 单次扫描

思路

在之前的基础上改进，假设遍历到数字c,查找哈希表 统计c+1，c-1出现次数，取结果较大值

这个思路可行在于 ，把问题转化为了以ith结尾的数字c 其最长和谐子序列长度

1
2
3
4
5
6
7
8
9
10
int findLHS(vector<int>& nums) {
        unordered_map<int,int> hash;
        int res=0;
        for(auto c:nums){
            hash[c]++;
            if(hash.count(c+1)) res=max(res,hash[c]+hash[c+1]);
            if(hash.count(c-1)) res=max(res,hash[c]+hash[c-1]);
        }
        return res;
    }

205. 同构字符串

解法1.hash统计第一次出现的字符位置

解法2.双射

两个哈希表存char->char
我们要判断字母之间是否一一对应，即判断 ss 中的相同字母是否对应到 tt 中的相同字母，且 tt 中的相同字母是否对应到 ss 中的相同字母。

我们用两个哈希表分别存储 ss 到 tt 和 tt 到 ss 的映射关系。
然后从前往后扫描字符串，判断相同字符是否都映射到相同字符。

时间复杂度分析：哈希表的插入、查找操作的时间复杂度是 O(1)，两个字符串均只扫描一遍，所以总时间复杂度是 O(n)。

290. 单词规律

给定一种规律 pattern 和一个字符串 str ，判断 str 是否遵循相同的规律。

这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应规律。

思路同lc205 一样 ,两种方法都可以

  1. 哈希表存字符(单词)第一次出现的位置
  2. 哈希表分别存 单词->字符 字符->单词映射关系

这里新学到了一点 利用stringstream将”dog cat cat dog” 处理成vector

1
2
3
4
stringstream raw(str);
vector<string> strs;
string line;
while (raw >> line) strs.push_back(line);

完整代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool wordPattern(string pattern, string str) {
        stringstream ss(str);
        vector<string> vec;
        string line;
        while(ss>>line) vec.push_back(line);

        unordered_map<char,string> hash1;
        unordered_map<string,char> hash2;

        if(pattern.size()!=vec.size()) return false;

        for(int i=0;i<pattern.size();i++){
            if(!hash1.count(pattern[i])) hash1[pattern[i]]=vec[i];
            if(!hash2.count(vec[i]))  hash2[vec[i]]=pattern[i];
            if(hash1[pattern[i]]!=vec[i]||hash2[vec[i]]!=pattern[i]) return false 
        }
        return true;
        
    }

https://www.acwing.com/solution/content/335/

347. 前 K 个高频元素

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

面试题经常考

解法1.hash+sort

这个思路很直接

  • 先用hash table 统计词频
  • 将hash 转化为vector 进行排序(降序)
  • 返回前k个元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> map;
        for(auto c:nums) map[c]++;
        typedef pair<int,int> pii;
        vector<pii> vec;
        for(auto c:map) vec.push_back({c.second,c.first});
        sort(vec.begin(),vec.end(),greater<pii>());
        
        vector<int> res;
        for(int i=0;i<k;i++){
            res.push_back(vec[i].second);
        }
        return res;

    }

解法2. hash+优先队列

  • topk （前k大）用小根堆，维护堆大小不超过 k 即可。每次压入堆前和堆顶元素比较，如果比堆顶元素还小，直接扔掉，否则压入堆。检查堆大小是否超过 k，如果超过，弹出堆顶。复杂度是nlogk

  • 避免使用大根堆，因为你得把所有元素压入堆，复杂度是 nlogn，而且还浪费内存。如果是海量元素，那就挂了。
    [

求前 k 大，用小根堆，求前 k 小，用大根堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> topKFrequent(vector<int>& nums, int k) {
        
        unordered_map<int,int> hash;
        vector<int> res;
        for (int x : nums) hash[x] ++;
        priority_queue<pii,vector<pii>,greater<pii>> qu; //建立小根堆
        for(auto c:hash){
            qu.push({c.second,c.first});
            if(qu.size()>k) qu.pop();
        }
        while(qu.size()){
            res.push_back(qu.top().second);
            qu.pop();
        }
        
        return res;

面试题50. 第一个只出现一次的字符

在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。

这个算是旧题重写

一下还没转过来，老想着hash 无序呀，怎么找第一个出现次数为1的字符

1
2
3
4
5
6
char firstUniqChar(string s) {
        unordered_map<char,int> map;
        for(auto c:s) map[c]++;
        for(auto c:s) if(map[c]==1) return c;  //hash虽然无序  按照字符串的顺序遍历就ok，map是无序的
        return ' ';
    }

增强版 字节流动态查找 [-tag queue]

请实现一个函数用来找出字符流中第一个只出现一次的字符。

例如，当从字符流中只读出前两个字符”go”时，第一个只出现一次的字符是’g’。

当从该字符流中读出前六个字符”google”时，第一个只出现一次的字符是’l’。

如果当前字符流没有存在出现一次的字符返回#字符。

时间复杂度 均摊O(n)

思路
为什么能想到?
如果还是按照上上一题的做法,那么每查找一次就是O(n)，查找n次就是O(n^2)
于是我们需要优化, 一般这种优化不是双指针利用单调性就是用一些特殊的数据结构比如单调队列，单调栈

这道题目能用到单调性的原因:

假设我们有一个指针index指向第一次出现次数为1的元素,当我们再插入元素,index 只可能往后走，不可能往前走
反正法: 如果index 可以往前走， 根据其含义,就违背了index指向的当前位置为第一次出现次数为1的元素

用一个hash 记录出现的次数
queue 按照流的顺序来保存
维护这样一个队列: 队首就是第一次出现一次的字符,一旦不满足要求,就pop队首

1
2
3
4
5
6
7
8
9
10
 unordered_map<char,int>map;
    queue<char> qu;
//动态插入维护一个queue
    void insert(char ch){
        if(++map[ch]>1){
            while(qu.size()&&map[qu.front()]>1) qu.pop(); //队列不为空&&队首元素出现的次数>1
        }
        else qu.push(ch);
        
    }

525. 连续数组

给定一个二进制数组, 找到含有相同数量的 0 和 1 的最长连续子数组（的长度）

思路

  1. 将问题转化为求区间和为0 的最长值： 具体做法 遇到0加-1
  2. 开一个哈希表存储前缀和sum->index 映射 ,即第一次出现这个前缀和的下标
1
2
3
4
5
6
7
8
9
10
11
12
//问题在转化为 求最长连续子数组和为0
    int findMaxLength(vector<int>& nums) {
        unordered_map<int,int> map; // 前缀和->首次出现下标
        map[0]=-1;
        int s=0,res=0;
        for(int i=0;i<nums.size();i++){
            s+=nums[i]?1:-1;
            if(map.count(s)) res=max(res,i-map[s]); //
            else map[s]=i; //如果不存在说明这个前缀和第一次出现 记录下
        }
        return res;
    }

349/350. 数组交集

349.给定两个数组，编写一个函数来计算它们的交集。

示例 1:

输入:nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2]
350 输出[2,2]

选择合适的数据结构是解决问题的关键

对于349. 输出的每个元素是唯一的 数据结构用unordered_set

350 输出的元素可能重复, 选用unordered_multiset
注意在mutli里面如何删除一个特定的元素，而不是将其所有都删除

迭代器删除特定的元素， 就好像string 里面的erase() 可以范围删除(输入迭代器范围),也可以删除单个元素

1
2
3
4
5
6
7
8
9
10
11
12
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        unordered_multiset<int>st;
        vector<int> res;
        for(auto c:nums1) st.insert(c);
        for(auto c:nums2){
            if(st.count(c)){
                auto it=st.find(c); //查找迭代器
                res.push_back(c);
                st.erase(it);
            }
        }
        return res;

187. 重复的DNA序列

所有 DNA 都由一系列缩写为 A，C，G 和 T 的核苷酸组成，例如：“ACGAATTCCG”。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。

编写一个函数来查找 DNA 分子中所有出现超过一次的 10 个字母长的序列（子串）。

示例：

输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出：["AAAAACCCCC", "CCCCCAAAAA"]
思路
遍历字符串s, 提取长度为10的子串str,依次存到哈希表中,如果 ++hash[str]==2 就找到了一个满足要求的子串

这个处理真的很妙,++res==2 找到了满足要求的解，但是又不会重复将解push，省去了后面去重.

554. 砖墙

这个题目就绕了一点,需要做一下问题的转化 将穿过最少砖块转化为最大砖块重合

还有一点特别要注意你不能沿着墙的两个垂直边缘之一画线，这样显然是没有穿过一块砖的。

思路
对砖块的每一行, 求到当前砖块的前缀和,哈希表存前缀和->出现次数 映射
前缀和出现次数最多表示每一行在当前位置重合的砖块最多

1
2
3
4
5
6
7
8
9
10
11
12
13
int leastBricks(vector<vector<int>>& wall) {
        unordered_map<int,int>map;
        int res=0;
        for(auto blocks:wall){
            int s=0; //求每一行的前缀和
            for(int i=0;i+1<blocks.size();i++){ //i+1<size 避免沿着墙的右边缘
                s+=blocks[i];
                res=max(res,++map[s]);
            }
        }
        return wall.size()-res;
    }
};

1371. 每个元音包含偶数次的最长子字符串

给你一个字符串 s ，请你返回满足以下条件的最长子字符串的长度：每个元音字母，即 ‘a’，’e’，’i’，’o’，’u’ ，在子字符串中都恰好出现了偶数次。

  • 为啥hash[0]=-1

这是用哈希表存储val->index 套路做法

原因在于 区间[l,r]和为s[r]-s[l-1] 当r==l==0 即 nums[0]=s[0]-s[-1] 所以有s[-1]=0 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int findTheLongestSubstring(string s) {
        unordered_map<int,int> hash; // state code->index
        hash[0]=-1; 
        string nums="aeiou";
        int st=0,res=0;
        for(int i=0;i<s.size();i++){
            for(int j=0;j<5;j++){
                if(s[i]==nums[j]){
                    st^=1<<j;//异或 1^1=0 0^1=1 不进位加法
                }
            }
           // cout<<"i:"<<i<<"  state code:"<<st<<endl;
            if(hash.count(st))  res=max(res,i-hash[st]); // 表示区间段 st为0 即元音出现次数为偶数
            else hash[st]=i;
        }
        return res;
    }