本題鏈接??找到字符串中所有字母異位詞

第一步：了解題意

給定2個(gè)字符串s和p，找到s中所有p的變位詞的字串，就是p是"abc",在s串中找到與p串相等的字串，可以位置不同，但是字母必須相同，比如”bca","bac"等，都是可以被稱之為變位詞。最終返回與p串字母相等但排列不同的字符串的初始索引即可。

例如 P="abc" { "abc","acb","cab","cba"}都是它的異位詞。

S=“cbaebabacd" P="abc"

符合條件的2組"cba"起始索引是0，"bac"起始索引是6,所以結(jié)果是[0,6].

第二步：算法原理

首先看到這個(gè)題目我們就會(huì)想到如何快速判斷2個(gè)字符串是否是"異位詞"

• 統(tǒng)計(jì)字符串中字符出現(xiàn)個(gè)數(shù)統(tǒng)計(jì) 統(tǒng)計(jì)就用hash表

這時(shí)候我們就想到了hash表，哈希表用來記錄出現(xiàn)個(gè)數(shù)，對(duì)于下標(biāo)的映射。首先給hash表各個(gè)元素都設(shè)置成0，然后依次存入a計(jì)入，然后讓字符a的個(gè)數(shù)++，a的映射就是1，依次記錄。所以p和s的字符串都用hash表來記錄。

第一種解法：暴力枚舉+哈希

首先我們將P字符串依次存入hash1表中，Q字符串依次存入hash2表中。

定義2個(gè)指針都從頭開始，依次計(jì)入hash2表中，然后當(dāng)right-left+1>P字符串的長(zhǎng)度時(shí)候，我們就判斷倆個(gè)哈希表是否相等。然后清空hash2表。

再存入新的值之前我們需要給"cba"存入hash2表值去才能重新存入。

這樣我們看著肯定是很繁瑣的，為什么right要重新回到left下一個(gè)位置重新開始呢？為什么不right++呢？這就是可以優(yōu)化的地方。

所謂優(yōu)化就是：

right不往回跑，left往后++，就是刪除left所在的位置的值在hash2表中，增加right后面對(duì)應(yīng)的值存入hash2表中。

第二種解法：滑動(dòng)窗口+哈希

滑動(dòng)窗口的模板：

1.left=0,right=0;

2.進(jìn)窗口

3.判斷

4.出窗口

更新結(jié)果（這是是在上面的4個(gè)步驟中根據(jù)題目的不同來穿插的）

2.進(jìn)窗口

將right對(duì)應(yīng)的值存入到hash2表中去。

3.判斷

當(dāng)right-left+1>len(p),那么我們就要進(jìn)行判斷了。這時(shí)候開始出窗口了。

4.出窗口

出窗口其實(shí)就是left對(duì)應(yīng)的值從hash2表中刪除，然后left++即可。

肯定很多人想知道這里是如何更新結(jié)果的，我們?nèi)绾魏蚿字符串進(jìn)行判斷？

?5.更新結(jié)果

我們可以再進(jìn)窗口的時(shí)候就對(duì)其進(jìn)行操作為后續(xù)的更新結(jié)果奠定基礎(chǔ)。

主要進(jìn)行的步驟就是 進(jìn)窗口(后）對(duì)count的更新 和 出窗口(前）對(duì)count的更新

利用count變量來統(tǒng)計(jì)窗口中"有效字符"的個(gè)數(shù)

in和out就是對(duì)應(yīng)的字符

進(jìn)窗口：進(jìn)入后 hash2[in]<=hash1[in] count++;

出窗口:? 出去前?hash2[out]<=hash1[out] count--;

更新結(jié)果 count==len(p) ；

進(jìn)窗口+count維護(hù)

更新結(jié)果

出窗口+count維護(hù)

這就是進(jìn)窗口(后)和出窗口(前）進(jìn)行count維護(hù)。

第三步：實(shí)現(xiàn)代碼

class Solution {
public:
    vector<int> findAnagrams(string s, string p) 
    {
         int hashp[26]={0};//統(tǒng)計(jì)p字符串中各字符的個(gè)數(shù)
         vector<int>ret;//記錄結(jié)果
        for(auto ch:p) hashp[ch-'a']++;
         int hashs[26]={0};//統(tǒng)計(jì)s字符串中各字符的個(gè)數(shù)
         int left=0,right=0;
         int len=p.size(),count=0;
        while(right<s.size())
         {
            if(++hashs[s[right]-'a']<=hashp[s[right]-'a'])count++;//進(jìn)窗口+維護(hù)count
            if(right-left+1>len)//判斷
            {
                if(hashs[s[left]-'a']--<=hashp[s[left]-'a'])count--;//出窗口+維護(hù)count
                left++;
            }
            //更新結(jié)果
            if(count==len) ret.push_back(left);
            right++;
         }
         return ret;
    }
};

小知識(shí)：

正在寒假的提升版。文章來源地址http://www.zghlxwxcb.cn/news/detail-804304.html

到了這里，關(guān)于力扣精選算法100題——找到字符串中所有字母異位詞(滑動(dòng)窗口專題）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！