76题的题解就是sliding window的模板.

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
public String minWindow(String s, String t) {
if (s == null || t == null || s.length() == 0 || t.length() == 0 || s.length() < t.length())
return "";
Map<Character, Integer> charCount = new HashMap<>();
for (int i = 0; i < t.length(); i++) {
charCount.put(t.charAt(i), charCount.getOrDefault(t.charAt(i), 0) + 1);
}
int left = 0, right = 0, count = 0, minLeft = 0, minRight = 0, min = Integer.MAX_VALUE;

while (right < s.length()) {
// Move right pointer.
while (right < s.length()) {
if (charCount.containsKey(s.charAt(right))) {
charCount.put(s.charAt(right), charCount.get(s.charAt(right)) - 1);
if (charCount.get(s.charAt(right)) >= 0) {
count += 1;
}
}
if (count == t.length())
break;
right += 1;
}

// Test if out of bound.
if (right == s.length())
break;

// Move left pointer until not all chars in t are included in the window.
// left <= right可要可不要.
while (count == t.length() && left <= right) {
if (charCount.containsKey(s.charAt(left))) {
charCount.put(s.charAt(left), charCount.get(s.charAt(left)) + 1);
if (charCount.get(s.charAt(left)) > 0) {
count -= 1;
}
}
left += 1;
}

// Check the length.
if (right - (left - 1) + 1 < min) {
minLeft = left - 1;
minRight = right + 1;
min = right - (left - 1) + 1;
}

right += 1;
}
return min != Integer.MAX_VALUE ? s.substring(minLeft, minRight) : "";
}
}

还有一种求最大window的, 不缩版本, 1004是模板.
思路就是right不停移动, 等到某个时刻, window变成不valid的了, 此时right - left就是此时满足条件的window size(也就是不包含right这一端的window). 然后我们开始移动left, 一般都会记录window中的某个东西, 这个东西决定winodw是否valid, 比如1004是记录window中有多少个0, 如果left移动前是个0, 我们要及时更新0的count, 然后再移动left. 第3题是不能有重复字符, 于是我们记录window中重复的字符的数量, 如果left移动前指向的字符的freq是2, 那么我们就需要把重复字符的数量减去1, 然后再移动left.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public int longestOnes(int[] nums, int k) {
int left = 0, right, zeroCount = 0;
for (right = 0; right < nums.length; right++) {
if (nums[right] == 0)
zeroCount += 1;
if (zeroCount > k && nums[left++] == 0) {
zeroCount -= 1;
}
}
return right - left;
}
}

第3题算是练手了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public int lengthOfLongestSubstring(String s) {
int[] charCount = new int[256];
char[] sArray = s.toCharArray();
int left = 0, right = 0, repeatCount = 0;
for (right = 0; right < sArray.length; right++) {
char currChar = sArray[right];
charCount[currChar] += 1;
if (charCount[currChar] == 2) {
repeatCount += 1;
}
if (repeatCount > 0) {
charCount[sArray[left]] -= 1;
if (charCount[sArray[left]] == 1) {
repeatCount -= 1;
}
left += 1;
}
}
return right - left;
}
}