滑动窗口与哈希表
基本思想
滑动窗口: 即不断的调节目标子序列的起始位置与终止位置，不断与待比较序列比较，从而获得我们想要的结果。
哈希表:哈希表是根据关键码的值而直接进行访问的数据结构。
题目
给定两个字符串s和p，找到s中所有p的异位词的子串，返回这些子串的起始索引。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
示例:
输入: s = “cbaebabacd”, p = “abc”
输出: [0,6]
解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。
分析
- 首先根据Hash表特点。
统计序列中数值出现的个数，创建s和p的Hash数组。 - 将
p的Hash数组置于sHash数组初始位置进行长度 length = p.length 长度进行 +1 向右移动。 - 每次移动 +1 则比较此时两个Hsah数组是否相等，若相等则将左边界记录。
- 注意每次 +1 移动，则左边也会移动，同时将
sHash数组进行Hash数组对应数值 -1。
Java 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public List<Integer> findAnagrams(String s, String p) {
int sLen = s.length(),pLen = p.length();
//即s小于则无法存在异位数
if(sLen < pLen){
return new ArrayList<Integer>();
}
List<Integer> res = new ArrayList<Integer>();
//构建两个滑动hash数组
int[] sArry = new int[26];
int[] pArry = new int[26];
// 将活动数组放到s初始位置 即只会统计以plen为长度的hash
for(int i = 0; i < pLen;i++){
sArry[s.charAt(i) - 'a']++;
pArry[p.charAt(i) - 'a']++;
}
//判断s从i=0开始的hash数组是否相等
if(Arrays.equals(sArry,pArry)){
res.add(0);
}
//开始做滑动判断
for(int i = 0 ;i < sLen - pLen; i++){
//slen - plen 为截止 即大于位置 则后续的长度是小于plen 是不可能存在p的异位字符
//滑动窗口右边界移动
sArry[s.charAt(i+pLen) - 'a']++;
//左边界移动 即需要将移动后的记录-1
sArry[s.charAt(i) - 'a']--;
//如果相等 则将左边界添加到结果数组
if(Arrays.equals(sArry,pArry)){
res.add(i+1);
}
}
return res;
}
}