leetcode 438. Find All Anagrams in a String& 滑动窗口

写在前面

一道滑动窗口的题目，这类型的题目在面试过程中不多见，但是leetcode中已经出现了很多次，也算是一类比较有特点的题目了，这里整理出来。

题目描述

Given a string s and a non-empty string p, find all the start indices of p’s anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

Input: s: “cbaebabacd” p: “abc”

Output: [0, 6]

Explanation: The substring with start index = 0 is “cba”, which is an anagram of “abc”. The substring with start index = 6 is “bac”, which is an anagram of “abc”. Example 2:

Input: s: “abab” p: “ab”

Output: [0, 1, 2]

Explanation: The substring with start index = 0 is “ab”, which is an anagram of “ab”. The substring with start index = 1 is “ba”, which is an anagram of “ab”. The substring with start index = 2 is “ab”, which is an anagram of “ab”.

题目分析

本题是滑动窗口方法的一个应用，另外，本题处理hash的方式也是被经常使用的，需要注意。

哈希方式

分析题目，要找的是待查询序列的一个子序列，这个子序列可以是给定目标序列的任意顺序。我们首先要考虑如何满足所谓的任意顺序。这里很容易想到采取一种哈希策略，使包含目标序列的字符拥有相同的哈希值，从而任何顺序的字符序列都可以被快速识别出来。这样的想法是完全正确的，相比去产生所有可能的序列，这种方法无疑拥有更低的时间复杂度。这种方法还是比较好想到，只需要一个字符数组，保存目标序列各个字符出现的次数即可。这样，只要满足对应数组结构的子序列，就是一个符合要求的子序列。

滑动窗口（sliding window）

字符串匹配问题一个常见的解法就是滑动窗口了，我们利用上述得到的哈希数组，来移动滑动窗口，若窗口内的字符串满足该数组，我们就记录窗口左部的下标作为返回值之一。本题中，滑动窗口的大小是判断是否移动左侧下标的条件，只有滑动窗口的长度达到目标序列后，左侧下标才会前移一位。另外，本题中我们使用变量count来表示窗口内剩余的目标字符个数，该个数为0表示窗口内的字符是要求的字符，这个值会在窗口滑动过程中得到更新。根据这种思路，实现的代码如下：

class Solution { public: vector<int> findAnagrams(string s, string p) { if(p.size()>s.size()||p.size()==0) return {}; vector<int> candidates; vector<int> letters(26,0); auto pSize = p.size(); for(int i = 0;i<pSize;++i) { letters[p[i]-'a']++; } // int i = 0,j = i; int left = 0, right = 0; int count = pSize; while(right<s.size()) { if(letters[s[right++]-'a']-->=1) count--; if(count == 0) candidates.push_back(left); if(right-left== pSize && letters[s[left++]-'a']++>=0) count++; } // while(i<s.size()&&j<s.size()) { // if(letters[s[i]-'a']!=0&&j == 0) { // j = i; // auto temp = letters; // auto pos = j; // int count = 0; // while(count<pSize&&j<s.size()) { // temp[s[j]-'a']--; // if(temp[s[j]-'a']<0) break; // count++; // j++; // } // if(count == pSize) candidates.push_back(pos); // j = 0; // } // ++i; // } return candidates; } };

注释部分是使用普通方法去做的字符匹配，毫无疑问多出了很多次不必要的循环，导致最后可能出现的超时，滑动窗口的方法的时间复杂度明显是O（n）。