这是悦乐书的第228次更新，第240篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第95题（顺位题号是438）。给定一个字符串s和一个非空字符串p，找到s中p的字谜的所有起始索引。字符串仅由小写英文字母组成，字符串s和p的长度不会大于20,100。输出顺序无关紧要。例如：
输入：s：“cbaebabacd” p：“abc”
输出：[0,6]
说明：
起始索引等于0的子字符串是“cba”，它是“abc”的字谜。
起始索引等于6的子字符串是“bac”，它是“abc”的字谜。
输入：s：“abab”p：“ab”
输出：[0,1,2]
说明：
起始索引等于0的子字符串是“ab”，它是“ab”的字谜。
起始索引等于1的子字符串是“ba”，它是“ab”的字谜。
起始索引等于2的子字符串是“ab”，它是“ab”的字谜。
本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。
02 第一种解法
题目的意思是在s中寻找由p中字符任意组成的字符串的起始索引。我们可以先将p中的字符及其出现次数存入一个256大小的整型数组，然后使用循环，从s的第一位字符开始，如果从第1位到p的长度位的字符都能匹配，那么就将起始索引添加进list中。
第一，为了多次使用存有p字符及其出现次数的数组，我们使用Arrays.copyOf方法，每次复制出一个新数组来处理，不影响原数组中的值。
第二，如果当前字符作为起始无法匹配，那么就结束内层循环，进入s下一个字符继续开始。
第三，因为是连续判断p的长度位，所以外层循环的次数控制为s的长度减去p的长度，直接使用s的长度会报下标越界异常。
public List<Integer> findAnagrams(String s, String p) {
List<Integer> list = new ArrayList<Integer>();
if (s == null || s.length() == 0 || s.length() < p.length()) {
return list;
}
int[] arr = new int[256];
for (char ch : p.toCharArray()) {
arr[ch]++;
}
int len = p.length();
for (int i=0; i<=s.length()-len; i++) {
boolean isMatch = true;
int[] arr2 = Arrays.copyOf(arr, 256);
for (int j=i; j<i+len; j++) {
if (--arr2[s.charAt(j)] < 0) {
isMatch = false;
break;
}
}
if (isMatch) {
list.add(i);
}
}
return list;
}
03 第二种解法
对于第一种解法，我们可以再简化下，同样是使用256大小的整型数组，但是我们将s也添加进256大小的数组中去。
先从0开始，将p中的字符及其出现次数添加进pArr数组中，同时将s中的前p的长度个字符添加进sArr数组中，进行第一次的比较，如果两数组相同，那么就将索引0添加进list中。接着，开始循环处理s中剩下的字符。
从p的长度开始作为循环的起始索引，往sArr中添加当前字符出现的次数，同时将s中左边字符出现的次数进行移除，即往sArr中添加新数的同时，移除旧数，然后判断两数组是否相等，相等就将起始索引添加进list中。
在本解法中，判断两数组是否相同使用的是Arrays.equals方法。
public List<Integer> findAnagrams2(String s, String p) {
List<Integer> list = new ArrayList<Integer>();
if (s == null || s.length() == 0 || s.length() < p.length()) {
return list;
}
int[] pArr = new int[256];
int[] sArr = new int[256];
for(int i=0; i<p.length(); i++){
pArr[p.charAt(i)]++;
sArr[s.charAt(i)]++;
}
if (Arrays.equals(pArr, sArr)) {
list.add(0);
}
for (int j=p.length(); j<s.length(); j++) {
++sArr[s.charAt(j)];
--sArr[s.charAt(j-p.length())];
if (Arrays.equals(pArr, sArr)) {
list.add(j-p.length()+1);
}
}
return list;
}
04 第三种解法
使用双指针。先将p中的字符及其出现次数初始化进256大小的整型数组，然后定义三个变量，第一个指针从0开始，表示从左，第二个指针也从0开始，表示向右，第三个变量为count，初始值为p的长度。
每次进入循环时，都将右指针向前移动1个单位，如果当前s中的字符存在于数组中，count减1，如果count等于0，则表示已经找到了s中满足p长度的字符串，此时就将左指针添加进list中。如果右指针减去左指针的大小等于p的长度，说明已经判断完一个p长度的字符串了，就需要将左指针往前移动一个单位，并且左指针指向的字符存在于数组中，count加1，最后返回list。
public List<Integer> findAnagrams3(String s, String p) {
List<Integer> list = new ArrayList<Integer>();
if (s == null || s.length() == 0 || s.length() < p.length()) {
return list;
}
int[] arr = new int[256];
for (char ch : p.toCharArray()) {
arr[ch]++;
}
int left = 0, right = 0, count = p.length();
while (right < s.length()) {
if (arr[s.charAt(right++)]-- >= 1) {
count--;
}
if (count == 0) {
list.add(left);
}
if (right - left == p.length() && arr[s.charAt(left++)]++ >= 0) {
count++;
}
}
return list;
}
05 小结
算法专题目前已连续日更超过两个月，算法题文章95+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！