先給題
給定兩個字符串 s1 和 s2，寫一個函數(shù)來判斷 s2 是否包含 s1 的排列。
換句話說，第一個字符串的排列之一是第二個字符串的子串。
示例1:
輸入: s1 = "ab" s2 = "eidbaooo"
輸出: True
解釋: s2 包含 s1 的排列之一 ("ba").
示例2:
輸入: s1= "ab" s2 = "eidboaoo"
輸出: False
注意：
輸入的字符串只包含小寫字母
兩個字符串的長度都在 [1, 10,000] 之間
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/permutation-in-string
今天第一次，沒有看題解做出來了，時間和內(nèi)存還都可以的情況下。繼續(xù)加油！
以后就不談暴力破解了，一般這樣的題暴力破解都超時
說一說自己的想法
第一眼看到這個字符串匹配的問題，就想到了滑動窗口（雙指針），最近做這樣的題蠻多的。
（看了題解才知道我用的是雙指針，雙指針和滑動窗口并不是一摸一樣的，具體區(qū)別可以看https://blog.csdn.net/WizardWXY/article/details/113703470，感覺講的蠻好的）
我們先來理解一下題，題的意思是我們要判斷s2中是否存在一個與s1等長度的子數(shù)組，元素種類與元素個數(shù)與s1完全相同。有就返回1，沒有就返回0.
（一開始我是按照順序也一致做的，不管正序或者逆序。但后來發(fā)現(xiàn)理解錯題了。）
所以，我們要想辦法來記錄一下子字符串的的元素狀況，我們開辟一個長度為26的數(shù)組來記錄個元素的數(shù)量。這個數(shù)組來記錄s1字符串元素的情況。當(dāng)右指針移動時，判斷這個元素個數(shù)是否為0，不為0代表目前子字符串的元素種類和個數(shù)都沒問題，如果為0，就表明這個元素要么不存在，要么前面存在這個元素的數(shù)量已經(jīng)超過了s1中的，這時候我們就要左指針移動，并且要再把左邊移動出來的元素再記錄進去。
那么記下來的問題就是如何判斷查找出符合的情況以及左指針根據(jù)什么條件移動。（這也是最難的兩個點）
左指針一旦移動，就代表了當(dāng)前子字符串的元素種類或者數(shù)目不符合要求，左指針需要移動，那么左指針移動到什么地步，子字符串就符合了？
極限的情況，我們遇到了一個s1根本不存在的元素，那么此時子字符串肯定不符合要求了，讓left和right移動到這個元素的后面重新開始。
而如果我們遇到的元素是前面出現(xiàn)的元素，只是數(shù)量達不到要求，那么左指針只要移動到與該元素相同的那個元素的后面，我們就可以不用再移動了，此時子字符串肯定符合要求。
根據(jù)上面的兩種情況，我們可以得出，只要右指針指向的元素的可用值為0，我們左指針就要一直移動，直到左指針達到右指針的位置。當(dāng)左指針不再移動時，再來判斷右指針指向元素是否大于0（因為右指針指向的元素不存在，那么左指針就移動到右指針的位置，所以還需要在判斷一下數(shù)值），大于0，就說明這個元素是存在于s1的，記錄影響值，=0，就說明這個元素不存在，左指針繼續(xù)移動一位，跳過這個元素。
一開始我是這么想的，當(dāng)這個記錄數(shù)值的26位數(shù)組所有值都為0的時候，就代表著元素全部用完了，但這樣太費時了。
所以我們來找另一種判斷的方法。
假設(shè)一開始我們就沒遇到不符合的元素，那么右指針一直移動，當(dāng)這個子數(shù)組元素情況與s1相等時，此時我們就可以判斷它是符合條件的。這樣的話如果我們遇到不符合的元素，那么此時右指針減去左指針+1 一定是小于等于s1的長度的。
根據(jù)上述假設(shè)，我們就可以知道，當(dāng)判斷后如果右指針減去左指針+1（即當(dāng)前子數(shù)組長度）達到了s1的長度，那么我們就可以說存在符合題意的子數(shù)組了。
class Solution { public: bool checkInclusion(string s1, string s2) { int left = 0, right = 0; vector<int> v(26, 0); for (int i = 0; i < s1.length(); i++) v[(int)s1[i] - 97]++; while (right < s2.length()) { if (v[(int)s2[right] - 97] > 0) v[(int)s2[right] - 97]--; else { while (v[(int)s2[right] - 97] == 0 && left < right) { v[(int)s2[left] - 97]++; left++; } if (v[(int)s2[right] - 97] > 0) v[(int)s2[right] - 97]--; else left++; } right++; if (right - left == s1.length()) return 1; } return 0; } };
題解有兩種，一種是滑動窗口，一種是雙指針（和我想的一摸一樣），所以在這里我們就來說滑動窗口。
其實思路差不很多，我們依然是開辟數(shù)組來記錄元素的狀況。只不過這次我們是來記錄兩個子數(shù)組的情況。
要想符合題意，s2的子數(shù)組長度肯定是s1的長度，所以只要兩個數(shù)組的元素情況相同，我們就可以返回1。左指針跟著右指針移動，窗口的長度固定不變。
官方題解還對這個方法進行了優(yōu)化，我們可以只開辟一個數(shù)組來記錄情況，這個數(shù)組用來記錄上述方法中用來記錄元素狀況的兩個數(shù)組的差，判斷條件我們可以用一個diff來記錄他們的不同值，當(dāng)差不為0，就讓diff++，只要diff不為0，那么就不符合。
這是未優(yōu)化的
1 class Solution { 2 public: 3 bool checkInclusion(string s1, string s2) { 4 int n = s1.length(), m = s2.length(); 5 if (n > m) { 6 return false; 7 } 8 vector<int> cnt1(26), cnt2(26); 9 for (int i = 0; i < n; ++i) { 10 ++cnt1[s1[i] - 'a']; 11 ++cnt2[s2[i] - 'a']; 12 } 13 if (cnt1 == cnt2) { 14 return true; 15 } 16 for (int i = n; i < m; ++i) { 17 ++cnt2[s2[i] - 'a']; 18 --cnt2[s2[i - n] - 'a']; 19 if (cnt1 == cnt2) { 20 return true; 21 } 22 } 23 return false; 24 } 25 };
這是優(yōu)化的
1 class Solution { 2 public: 3 bool checkInclusion(string s1, string s2) { 4 int n = s1.length(), m = s2.length(); 5 if (n > m) { 6 return false; 7 } 8 vector<int> cnt(26); 9 for (int i = 0; i < n; ++i) { 10 --cnt[s1[i] - 'a']; 11 ++cnt[s2[i] - 'a']; 12 } 13 int diff = 0; 14 for (int c: cnt) { 15 if (c != 0) { 16 ++diff; 17 } 18 } 19 if (diff == 0) { 20 return true; 21 } 22 for (int i = n; i < m; ++i) { 23 int x = s2[i] - 'a', y = s2[i - n] - 'a'; 24 if (x == y) { 25 continue; 26 } 27 if (cnt[x] == 0) { 28 ++diff; 29 } 30 ++cnt[x]; 31 if (cnt[x] == 0) { 32 --diff; 33 } 34 if (cnt[y] == 0) { 35 ++diff; 36 } 37 --cnt[y]; 38 if (cnt[y] == 0) { 39 --diff; 40 } 41 if (diff == 0) { 42 return true; 43 } 44 } 45 return false; 46 } 47 };
想詳細了解的可以去這里https://leetcode-cn.com/problems/permutation-in-string/solution/zi-fu-chuan-de-pai-lie-by-leetcode-solut-7k7u/
