哈希表unordered_map应用

1.  
   class Solution {
2.  
   public:
3.  
   vector<vector<string>> groupAnagrams(vector<string>& strs) {
4.  
   /* 根据返回值定义存储结果的变量 */
5.  
   vector<vector<string>> result;
6.  
    
7.  
   unordered_map<string, vector<string>> map;
8.  
   for (string& str: strs) {
9.  
   string key = str;
10.  
    /* 将串排序后便于同一作为键 */
11.  
    sort(key.begin(), key.end());
12.  
    /* 将相同键值的字符串放入vector容器中 */
13.  
    map[key].push_back(str);//emplace_back
14.  
    }
15.  
    /* 取出相同键值的vector */
16.  
    for (auto it = map.begin(); it != map.end(); it)
17.  
    result.push_back(it->second);
18.  
     
19.  
    return result;
20.  
    }
21.  
    };

知识点：auto原理是根据后面的值来推测auto的类型，其实就是简化初始化。

unordered_map底层的原理就是哈希表

思路：将每个字符串排序，排序后字符串相同的肯定是字母异位词，将相同的键值的字符串放入同一个vector容器当中。

我先开始想法（超时）

1.  
   class Solution {
2.  
   public:
3.  
   vector<int> findAnagrams(string s, string p) {
4.  
   vector<int> res;
5.  
   if (s.size() < p.size()) {
6.  
   return res;
7.  
   }
8.  
   unordered_map<string,vector<int>> map;
9.  
   int slowIndex = 0;
10.  
    int fastIndex = p.size() - 1;
11.  
    while (fastIndex < s.size()) {
12.  
    string temp = s.substr(slowIndex,p.size());
13.  
    sort(temp.begin(), temp.end());
14.  
    map[temp].push_back(slowIndex);
15.  
    slowIndex ;
16.  
    fastIndex ;
17.  
    }
18.  
    sort(p.begin(),p.end());
19.  
    return map[p];
20.  
    }
21.  
    };

 正确思路

1.  
   class Solution {
2.  
   public:
3.  
   vector<int> findAnagrams(string s, string p) {
4.  
   int sLen = s.size(), pLen = p.size();
5.  
    
6.  
   if (sLen < pLen) {
7.  
   return vector<int>();
8.  
   }
9.  
    
10.  
    vector<int> ans;
11.  
    vector<int> sCount(26);
12.  
    vector<int> pCount(26);
13.  
    for (int i = 0; i < pLen; i) {
14.  
    sCount[s[i] - 'a'];
15.  
    pCount[p[i] - 'a'];
16.  
    }
17.  
     
18.  
    if (sCount == pCount) {
19.  
    ans.emplace_back(0);
20.  
    }
21.  
     
22.  
    for (int i = 0; i < sLen - pLen; i) {
23.  
    --sCount[s[i] - 'a'];
24.  
    sCount[s[i pLen] - 'a'];
25.  
     
26.  
    if (sCount == pCount) {
27.  
    ans.emplace_back(i 1);
28.  
    }
29.  
    }
30.  
     
31.  
    return ans;
32.  
    }
33.  
    };

思想：利用哈希表和滑动窗口。

这篇好文章是转载于：学新通技术网