567.字元串中的排列
滑動窗口
給你兩個字元串 s1 和 s2 ，寫一個函數來判斷 s2 是否包含 s1 的排列。如果是，返回 true ；否則，返回 false 。
換句話說，s1 的排列之一是 s2 的 子串 。
示例 1：
輸入：s1 = “ab” s2 = “eidbaooo”
輸出：true
解釋：s2 包含 s1 的排列之一 (“ba”).
示例 2：
輸入：s1= “ab” s2 = “eidboaoo”
輸出：false
如果s2的某一子串是s1的排列，則返回true，否則返回false。首先要滿足這個條件，s2的長度一定要大於等於s1的長度，即：
if (s1.length() > s2.length()) {
return false;
}
字元串中保存的是小寫字母，可以用一個大小為26的數組來保存s1中字母出現的次數，因為滿足條件的s2的子串長度一定等於s1的長度，所以在s2中維護一個長度為s1的長度的滑動窗口，同樣用一個數組來表示該窗口中字母出現的次數：
int[] arr1 = new int[26];
for (int i = 0; i < s1.length(); i++) {
arr1[s1.charAt(i) - 'a']++;
}
int[] arr2 = new int[26];
for (int i = 0; i < s1.length(); i++) {
arr2[s2.charAt(i) - 'a']++;
}
因為s1是排列，所以只要窗口中的元素全部在s1中出現，則說明該窗口是s1的一個排列，這樣我們就只需要比較每次滑動窗口後兩個數組是否相同了，維護滑動窗口數組即每次去掉最左邊元素的同時將最右邊即將進入窗口元素加進來，通俗點講就是把要出窗口的元素在數組中-1，要加進來的元素在數組中+1。
整體程式碼如下：
class Solution {
public boolean checkInclusion(String s1, String s2) {
if (s1.length() > s2.length()) { //如果s1的長度大於s2的長度，則條件不可能成立，直接返回
return false;
}
int[] arr1 = new int[26];
for (int i = 0; i < s1.length(); i++) { //將s1保存在一個大小為26的數組中
arr1[s1.charAt(i) - 'a']++;
}
int[] arr2 = new int[26];
for (int i = 0; i < s1.length(); i++) { //創建窗口，窗口長度應該為s1的長度
arr2[s2.charAt(i) - 'a']++;
}
if (equals(arr1, arr2)) { //判斷兩個數組是否相同，相同則返回true
return true;
}
for (int i = 0; i < s2.length() - s1.length(); i++) { //維護滑動窗口
arr2[s2.charAt(i) - 'a']--; //去掉出窗口的元素
arr2[s2.charAt(i + s1.length()) - 'a']++; //加入進入窗口的元素
if (equals(arr1, arr2)) { //判斷兩個數組是否相同，相同則返回true
return true;
}
}
return false; //遍歷完s2後還沒有找到符合條件的子串則返回false
}
boolean equals(int[] arr1,int[] arr2) { //判斷兩個數組是否相等
for (int i = 0; i < 26; i++) {
if (arr1[i] != arr2[i]) {
return false;
}
}
return true;
}
}
原文：//leetcode.cn/problems/permutation-in-string/solution/by-nice-hermann9a2-dmbm/
