# 用法
窗口[i, j]
,j往后移的时候,i
使用滑动窗口的必要条件,即单调性:假设我们维护的窗口是[i, j]
,j往后走的时候,确保i不会往前走。
考虑这样一个题目:
# 560. 和为K的子数组 (opens new window)
给定一个整数数组和一个整数 **k,**你需要找到该数组中和为 k 的连续的子数组的个数。
示例 1 :
输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
2
说明 :
- 数组的长度为 [1, 20,000]。
- 数组中元素的范围是 [-1000, 1000] ,且整数 k 的范围是 [-1e7, 1e7]。
单调性:假设当前维护的窗口[i, j]
满足区间和等于k,如果j往后走,i是可以往前走的,因为nums[j+1]
可能是负数,此时i可以通过往前走加一些正数可能保证区间和为k,所以此处不能够使用双指针算法。
如果数组全为正数,那么可以使用双指针算法。
# 一些经典的题目
# 3. 无重复字符的最长子串 (opens new window)
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
2
3
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
2
3
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
2
3
4
确认单调性:维护一个窗口[i, j]
,假设当前窗口维护的是以字符j结尾的无重复字符的最长子串,如果j往后移了一位,假设i能够往前移一个字符且满足当前窗口是以字符j+1结尾的无重复字符的最长子串,那么就与假设条件矛盾了,如果能移,那么假设条件的窗口应该是[i-1, j]
。
思路:用滑动窗口来做,i,j指针分别指向窗口的开始和结尾,将j处的字符加入set集合,j++,表示扩大窗口,如果窗口内包含重复元素,缩小窗口,直到不包含重复元素,然后再继续扩大窗口。答案就是所有满足条件的窗口中的最大的窗口。
class Solution {
public int lengthOfLongestSubstring(String s) {
if(s == null)
return 0;
Set<Character> set = new HashSet<>();
int i = 0;
int j = 0;
int ans = 0;
while(j < s.length()){
char c = s.charAt(j++);
// 窗口内包含重复字符的时候,缩小窗口,直到不包含该字符
while(i <= j && set.contains(c)){
set.remove(s.charAt(i++));
}
set.add(c);
// 这个时候窗口内的元素都是不重复的,窗口内的元素就是set集合中的元素,这个时候更新最优的答案
ans = Math.max(ans, j - i);
}
return ans;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 76. 最小覆盖子串 (opens new window)
给你一个字符串 S、一个字符串 T,请在字符串 S 里面找出:包含 T 所有字符的最小子串。
示例:
输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
2
确认单调性:如果当前窗口[i, j]
满足包含T所有字符,j往后走i不会往前走,因为如果i往前走它的窗口大小没有[i, j]
小,也就没有意义。
思路:用哈希表need记录T中的每个字符出现的次数,用哈希表window表示窗口内各个元素出现的次数,用变量match表示窗口内与T中字符的匹配数。
当新加入一个字符c时,同时将字符c加入window中,如果此时window中c字符出现的次数 <= need中c字符出现的次数,就产生了一个匹配,此时match++。
当match == T.length()
时,表明窗口内包含了T中的所有字符,由于我们要找的是包含T所有字符的最小子串,所以这时候要尽可能缩小窗口,将一个字符c移出窗口时,同时将字符c在window中的次数减一,如果此时window中字符c的次数<need中字符c的出现的次数,就去掉了一个匹配,此时match--。
class Solution {
public String minWindow(String s, String t) {
HashMap<Character, Integer> need = new HashMap<>();
HashMap<Character, Integer> window = new HashMap<>();
for(int i = 0; i < t.length(); i++){
char c = t.charAt(i);
need.put(c, need.getOrDefault(c, 0) + 1);
}
int n = t.length(); // 总匹配数
int i = 0;
int j = 0;
int start = 0;
int minLen = Integer.MAX_VALUE;
int match = 0; // 当前窗口匹配数
while(j < s.length()){
char c = s.charAt(j++);
window.put(c, window.getOrDefault(c, 0) + 1);
if(window.get(c) <= need.getOrDefault(c, 0)){ // 产生一个匹配
match++;
}
while(match >= n){ // 满足条件下缩小窗口
if(minLen > j - i){ // 在此处更新最优
minLen = j - i;
start = i;
}
c = s.charAt(i++);
window.put(c, window.get(c) - 1);
if(window.get(c) < need.getOrDefault(c, 0)){ // 减少一个匹配
match--;
}
}
}
return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}
}
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
# 567. 字符串的排列 (opens new window)
给定两个字符串 s1 和 s2,写一个函数来判断 s2 是否包含 s1 的排列。
换句话说,第一个字符串的排列之一是第二个字符串的子串。
示例1:
输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").
2
3
示例2:
输入: s1= "ab" s2 = "eidboaoo"
输出: False
2
class Solution {
public boolean checkInclusion(String s1, String s2) {
Map<Character, Integer> m1 = new HashMap();
Map<Character, Integer> m2 = new HashMap();
int i = 0;
int j = 0;
int m = s1.length();
for(char c : s1.toCharArray()){
m1.put(c, m1.getOrDefault(c, 0) + 1);
}
while(j < s2.length()){
char c = s2.charAt(j++);
m2.put(c, m2.getOrDefault(c, 0) + 1);
if(j - i > m){ // 缩小窗口使窗口大小固定为m
c = s2.charAt(i++);
m2.put(c, m2.getOrDefault(c, 0) - 1);
if(m2.get(c) == 0)
m2.remove(c);
}
if(m2.equals(m1))
return true;
}
return false;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 通用模板
在模板中,注意需要特判窗口为0的情况
不定长窗口大小(求最大窗口)
while(j < s.length()){
// 将j处的值更新到窗口
j++;
while(窗口不满足条件,缩小窗口){
// 将i处的值从窗口移除
i++;
}
// 更新最优
}
2
3
4
5
6
7
8
9
不定长窗口大小(求最小窗口)
while(j < s.length()){
// 将j处的值更新到窗口
j++;
while(窗口满足条件){
// 更新最优
// 将i处的值从窗口移除
i++;
}
}
2
3
4
5
6
7
8
9
窗口大小一定,为m
while(j < s.length()){
// 将j处的值更新到窗口
j++;
if(j - i > m){
// 将i处的值从窗口移除
i++;
}
if(j - i == m){
// 更新最优
}
}
2
3
4
5
6
7
8
9
10
11
特别注意更新最优语句应该能够在窗口符合条件时都能够走得到。