滑动窗口
久等了~
滑动窗口的特点是左右两端有两个指针标注着窗口左右界限。
如果我们要找一个满足需求的固定长度的窗口：记录下当前窗口与目标窗口之间的差异，每次循环剔除掉左侧元素，加入右侧新元素并再次比较。这样不用双层循环每次都重新遍历目标窗口长度。
如果要找一个非固定长度的窗口：右侧不断延伸，如果出现不满足条件的情况，则左侧指针也向右移动直到新窗口再次满足条件为止。随后右侧指针继续延伸。
3. 无重复字符的最长子串
这道题对应上面我们说过的第二种滑动窗口情况。
- 左指针从0开始，右指针从1开始滑动（当然首先要考虑字符串长度<=1的情况）。
- 右侧窗口指针不断滑动，如果每次滑动没有出现重复字符则当前长度+1，并判断是否要更新最大长度。
- 如果右侧窗口指针出现了该窗口中已经出现过的重复元素，则左侧窗口指针向右移动直到略过重复元素出现的位置，形成新窗口。此时不用判断新窗口长度是否为最大长度，因为右侧向右移动了1，左侧向右至少移动了1，长度不可能变得比上一轮循环的窗口长度更长。
比如对于示例1：
起始窗口： ptr_left=0, ptr_right=1, (ab), window_length=2
第一次移动： ptr_left=0, ptr_right=2, (abc), window_length=3
第二次移动： ptr_left=0, ptr_right=3, (abca)，出现重复元素。则左指针向右移动直到不再出现重复元素为止：ptr_left=1, ptr_right=3, (bca)
第三次移动： ptr_left=1, ptr_right=4, (bcab)，出现重复元素。则左指针向右移动直到不再出现重复元素为止：ptr_left=2, ptr_right=4, (cab)
……
至于窗口中是否重复元素的判断方式，最优解还是哈希表查找。遍历我觉得也还行吧。
class Solution {
public int lengthOfLongestSubstring(String s) {
if (s == null || s.length() == 0)
return 0;
int left = 0, right = 1, max_length = 1;
Set<Character> set = new HashSet<Character>();
set.add(s.charAt(left));
while (right < s.length()) {
if (!set.add(s.charAt(right))) {
int i = left;
while (s.charAt(i) != s.charAt(right)) {
set.remove(s.charAt(i));
i++;
}
left = i + 1;
} else {
if (right - left + 1 > max_length) {
max_length = right - left + 1;
}
}
right++;
}
return max_length;
}
}
438. 找到字符串中所有字母异位词
这种属于我们介绍的滑动窗口第一种情况：固定窗口长度。
对于待检索的字符串 s，我们可以先存储 [0, p.length()-1] 范围的一个窗口范围的子串。随后每轮循环中舍弃掉左侧的一个元素，添加右侧的一个新元素，重点关注增加这两处变动后新子串和目标子串的差异变化。
关于差异，题解采取了用长度为26的数组记录字符差异的方法。目标子串中有而当前子串中没有的记为+1，当前子串中有而目标子串中没有的记为-1. 当数组所有元素求和=0 的话说明当前窗口子串和目标子串无差异。
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> return_list = new ArrayList<Integer>();
if (s.length() < p.length())
return return_list;
int[] count = new int[26];
for (int i = 0; i < p.length(); i++) {
count[p.charAt(i) - 'a']++;
count[s.charAt(i) - 'a']--;
}
int differ = 0;
for (int i = 0; i < 26; i++) {
if (count[i] != 0)
differ++;
}
if (differ == 0)
return_list.add(0);
for (int i = 0; i < s.length() - p.length(); i++) {
if (count[s.charAt(i) - 'a'] == -1) {
--differ;
} else if (count[s.charAt(i) - 'a'] == 0)
++differ;
count[s.charAt(i) - 'a']++;
if (count[s.charAt(i + p.length()) - 'a'] == 1) {
--differ;
} else if (count[s.charAt(i + p.length()) - 'a'] == 0)
++differ;
count[s.charAt(i + p.length()) - 'a']--;
if (differ == 0)
return_list.add(i + 1);
}
return return_list;
}
}