一开始以为只是简单的找子串，结果，是找子串的排列，我能想到的是暴力解法，也算是变相的滑动窗口，只是我是用HashMap来记录s1的（单）词频，官方解题是用数组。我觉得这题的关键点在通过比较字母数量来判断是否为子串的排列。【由于排列不会改变字符串中每个字符的个数，所以只有当两个字符串每个字符的个数均相等时，一个字符串才是另一个字符串的排列。】话不多说，直接上解题思路和代码！
以下是三种解题方式：
方法1：双循环
采用双循环，外层循环是窗口移动，内层循环是大小为n1(即s1的长度）的窗口。用HashMap来记录词频。
class Solution {
public boolean checkInclusion(String s1, String s2) {
// 1.暴力解法，双循环。借助HashMap，比较字母数量来判断是否为子串排列——时间复杂度和空间复杂度都高
HashMap<Character,Integer> map=new HashMap<>();
int n1=s1.length();
int n2=s2.length();
char c;
HashMap<Character,Integer> copy;
if(n1>n2) return false; // 条件判断
for(int i=0;i<n1;i++){ // 构建hashmap,key:字符，value:计数
c=s1.charAt(i);
map.merge(c,1,Integer::sum);
}
for(int i=0;i<=n2-n1;i++){
int j=i;
copy=(HashMap<Character,Integer>)map.clone();
for(;j<i+n1;j++){
c=s2.charAt(j);
int v=copy.getOrDefault(c,-1);
if(v>0)
copy.put(c,v-1);
else
break;
}
if(j==i+n1)
return true;
}
return false;
}
}方法2：巧妙的滑动窗口——“你进一尺，我退一步”
class Solution {
public boolean checkInclusion(String s1, String s2) {
// 3.滑动窗口：用两个数组cnt1和cnt2分别统计s1的字母数量和s2中窗口大小为n1的字母数量是否相等
int n1=s1.length();
int n2=s2.length();
int[] cnt1=new int[26];
int[] cnt2=new int[26];
if(n1>n2) return false;
for(int i=0;i<n1;i++){ // 统计s1的（单）词频
cnt1[s1.charAt(i)-'a']++;
cnt2[s2.charAt(i)-'a']++;
}
if(Arrays.equals(cnt1,cnt2)) return true;
for(int i=n1;i<n2;i++){ // 滑动窗口：进一尺，退一步
cnt2[s2.charAt(i)-'a']++;
cnt2[s2.charAt(i-n1)-'a']--;
if(Arrays.equals(cnt1,cnt2)) return true;
}
return false;
}
}方法3：双指针
class Solution {
public boolean checkInclusion(String s1, String s2) {
// 4.双指针，让cnt用s1初始化，然后根据cnt[i]是否小于0，找到长度为n的子串
int n1=s1.length();
int n2=s2.length();
int[] cnt=new int[26];
int start=0,end=0;
for(int i=0;i<n1;i++)
cnt[s1.charAt(i)-'a']--;
for(;end<n2;end++){
int x=s2.charAt(end)-'a';
cnt[x]++;
while(cnt[x]>0){ //start指针右移到end
cnt[s2.charAt(start)-'a']--;
start++;
}
if(end-start+1==n1) return true;
}
return false;
}
}参考：
