门户网站首页模板广州网站建设网站优化推广

Problem: 438. 找到字符串中所有字母异位词

预备知识

此题用到了双指针算法中的滑动窗口思想，以及哈希表的运用。c++中是unordered_map。如果对此不了解的uu，建议查看相关介绍博客和更简单的题目！！！

解题思路

该题解法为：滑动窗口 + 哈希表。

1. 该题的滑动窗口是固定的，我们只需要对每次移动新字符和删除字符进行判断，时间复杂度为O(n)。

2. 首先，定义一个哈希表，记录要满足匹配p字符串需要多少的对应的字符。

   unordered_map<char, int> pp;
   

3. 遍历p，出现对应的字符，就在该位置的–，说明还需要在s中找多少该字符。

   while (j < p.size()) {  //O(1) 理论上子字符串的操作应该是1//开始遍历，在s上初始化第一个字符串，能够满足对应字符供给的就++pp[s[j++]]++;
   }
   

4. 遍历pp，如果不为0，说明该子字符串不满足匹配条件，则跳到x.

   for (auto& [a, b] : pp) {   //O(1) max=26//遍历pp，如果不为0，说明该子字符串不满足匹配条件，则跳到xif (b != 0) goto x;
   }
   

5. 最后进行全局遍历

   while (j < s.size()) {  //O(n)//开始遍历//对于j位置的字符，将pp对应位置++，表示提供一个字符pp[s[j]]++;//对于i位置的字符，将pp对应位置--，表示不能提供一个字符pp[s[i]]--;for (auto& [a, b] : pp) {   //O(1) max=26if (b != 0) goto xx;}v.push_back(i + 1);xx:;i++;j++;
   }
   

复杂度

时间复杂度:

O(26 * n)，26是遍历哈希表中的每种英文字母的个数，最多为26，n是遍历滑动窗口。

空间复杂度:

O(26 + n)，26是哈希表最大size，n是vector最大size。

Code

class Solution {
public:vector<int> findAnagrams(string s, string p) {//记录要满足匹配p字符串需要多少的对应的字符unordered_map<char, int> pp;    vector<int> v;int i = 0, j = 0;for (auto a : p) {  //O(n)//遍历p，出现对应的字符，就在该位置的--，说明还需要多少该字符pp[a]--;}while (j < p.size()) {  //O(1) 理论上子字符串的操作应该是1//开始遍历，在s上初始化第一个字符串，能够满足对应字符供给的就++pp[s[j++]]++;}for (auto& [a, b] : pp) {   //调试bug的时候可以用输出的方法cout << a << b << endl;}for (auto& [a, b] : pp) {   //O(1) max=26//遍历pp，如果不为0，说明该子字符串不满足匹配条件，则跳到xif (b != 0) goto x;}v.push_back(i);x:;while (j < s.size()) {  //O(n)//开始遍历//对于j位置的字符，将pp对应位置++，表示提供一个字符pp[s[j]]++;//对于i位置的字符，将pp对应位置--，表示不能提供一个字符pp[s[i]]--;for (auto& [a, b] : pp) {   //O(1) max=26if (b != 0) goto xx;}v.push_back(i + 1);xx:;i++;j++;}return v;}
};

其它细节

可以尝试用输出日志的方式来获得局部代码的正确性。对于比较长的代码，我们应该在写完整个代码之前，已经完成多个地方的日志输出。多加练习能够提高自己写代码的正确性。

for (auto& [a, b] : pp) {   //调试bug的时候可以用输出的方法cout << a << b << endl;
}

推荐博客或题目

博客

1. 滑动窗口详解
2. 哈希表理论基础

题目

滑动窗口

1. 无重复字符的最长子串 难度：++

哈希表

1. 两数之和 难度：++
2. 三数之和 难度：+++
3. 四数之和 难度：++++
4. 四数相和II 难度：++++