题目大意：
字符串的排列
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
换句话说，第一个字符串的排列之一是第二个字符串的子串。
示例1:
输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").示例2:
输入: s1= "ab" s2 = "eidboaoo" 输出: False
注意：
- 输入的字符串只包含小写字母
- 两个字符串的长度都在 [1, 10,000] 之间
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=567
解题思路分析：
如果s1的任意一种排列是s2的一个子串，那么说明s1中每种字母的个数要与s2某个子串所有字母个数完全相同，因此，本题首先要统计出s1中所包含的每种字母数量，将其保存在数组count中。然后使用双指针方式来遍历s2，起始时，左右两指针均在第0位。利用右指针不断加一来查看当前字符，在count数组中，当前字符的数量减一。减一操作后，如果count的值为0，说明当前字符消耗掉了所有s1中的当前字符，这时查看一下左右区间的长度，如果该长度等于s1的长度，那么说明当前区间可以匹配上s1，直接返回true。如果count值为-1，说明当前字符不存在于s1中，或者当前区间内的当前字符数量多于s1中的数量，此时向右逐步移动左指针，左指针经过的位置表示已经移出区间，此时在count数组中要对相应的字符个数加一，直到出现左指针与右指针指向了相同的字符为止，右指针所指的字符个数count由-1变为0，接下来继续移动右指针，重复上述操作。
实现代码：
public boolean checkInclusion(String s1, String s2) {
// 统计s1中所有字母数量
int[] count = new int[26];
for(int i=0;i<s1.length();i++){
count[s1.charAt(i)-'a']++;
}
// 定义左右指针
int left=0, right=0;
while(left<s2.length()&&right<s2.length()){
// 当前字符
int c = s2.charAt(right)-'a';
// 当前字符数量减一
count[c]--;
// 如果当前数量为0
if(count[c] == 0){
// 区间长度正好等于s1长度时，说明完全匹配，返回true
if(right-left+1==s1.length()) return true;
}else if(count[c]<0){ // 如果当前数量小于0
// 移动左指针
while(left<=right){
// 左指针字符
int leftChar = s2.charAt(left++)-'a';
// 左指针字符数量加一
count[leftChar]++;
// 左右指针字符相同时，结束移动左指针
if(leftChar==c){
break;
}
}
}
right++; // 右指针加一
}
return false;
}本题解法执行时间为5ms。
Runtime: 5 ms, faster than 80.89% of Java online submissions for Permutation in String.
Memory Usage: 37.3 MB, less than 88.46% of Java online submissions for Permutation in String.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-567-permutation-in-string-解题思路分析/