「滑动窗口」专题 :滑动窗口的基本思想
在滑动窗口类型的问题中都会有两个指针。一个用于延伸现有窗口的 right
指针,和一个用于收缩窗口的 left
指针。在任意时刻,只有一个指针运动,而另一个保持静止。
「滑动窗口」的问题其实思想并不难,但是在有一定的编码量,如果一不小心还有可能出错。在这里解决边界问题的一个小技巧,就是所谓的「循环不变量」。在这里再和大家总结一下:
- 这里「循环不变量」的定义是一个空区间(如果不是空区间,也要满足定义);
- 这个区间一开始的时候是一个空区间;
- 在遍历的过程中,维持循环不变量的定义;
- 在遍历完成以后,滑动窗口完成了所有可能的情况而不会错过最优解。
需要使用一些变量去描述「滑动窗口」内元素的性质,这里需要根据具体问题具体设计。
对于一个固定的左端点,满足条件的右端点的集合是连续的,但是题目只要我们求最值。
右端点主动,左端点被动。
例 1:「力扣」第 3 题:无重复字符的最长子串(滑动窗口典型问题)
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
Java 代码:
public class Solution {
public int lengthOfLongestSubstring(String s) {
int len = s.length();
if (len < 2) {
return len;
}
char[] charArray = s.toCharArray();
// 描述 [left, right) 里是否有元素的变量
int[] hashMap = new int[128];
// [left, right) 无重复的元素
int res = 1;
for (int left = 0, right = 0; right < len; right++) {
hashMap[charArray[right]]++;
if (hashMap[charArray[right]] == 2) {
while (hashMap[charArray[right]] == 2) {
hashMap[charArray[left]]--;
left++;
}
}
res = Math.max(res, right - left + 1);
}
return res;
}
}
例 2:「力扣」第 76 题:最小覆盖子串
给定一个字符串
S
和一个字符串T
,请在S
中找出包含T
所有字母的最小子串。
Java 代码:
public class Solution {
public String minWindow(String s, String t) {
int sLen = s.length();
int tLen = t.length();
if (sLen == 0 || tLen == 0) {
return "";
}
int[] countS = new int[256];
int[] countT = new int[256];
char[] charArrayS = s.toCharArray();
char[] charArrayT = t.toCharArray();
int distance = 0;
for (char charT : charArrayT) {
if (countT[charT] == 0) {
distance++;
}
countT[charT]++;
}
int minLen = sLen + 1;
int left = 0;
int right = 0;
int count = 0;
int begin = 0;
while (right < sLen) {
if (countT[charArrayS[right]] == 0) {
right++;
continue;
}
countS[charArrayS[right]]++;
if (countS[charArrayS[right]] == countT[charArrayS[right]]) {
count++;
}
right++;
while (count == distance) {
if (right - left < minLen) {
minLen = right - left;
begin = left;
}
if (countT[charArrayS[left]] > 0) {
countS[charArrayS[left]]--;
if (countS[charArrayS[left]] < countT[charArrayS[left]]) {
count--;
}
}
left++;
}
}
if (minLen == sLen + 1) {
return "";
}
return s.substring(begin, begin + minLen);
}
public static void main(String[] args) {
Solution solution = new Solution();
String S = "ADOBECODEBANC";
String T = "ABC";
String minWindow = solution.minWindow(S, T);
System.out.println(minWindow);
}
}
例 3:第 438 题:找到字符串中所有字母异位词
给定一个字符串 s 和一个非空字符串 p,找到 s 中所有是 p 的字母异位词的子串,返回这些子串的起始索引。
字符串只包含小写英文字母,并且字符串 s 和 p 的长度都不超过 20100。
Java 代码:
import java.util.ArrayList;
import java.util.List;
public class Solution {
public List<Integer> findAnagrams(String s, String p) {
int sLen = s.length();
int pLen = p.length();
List<Integer> res = new ArrayList<>();
if (sLen == 0 || pLen == 0) {
return res;
}
int[] text = new int[128];
int[] pattern = new int[128];
char[] charArrayP = p.toCharArray();
int distance = 0;
for (char c : charArrayP) {
if (pattern[c] == 0) {
distance++;
}
pattern[c]++;
}
int left = 0;
int right = 0;
int count = 0;
char[] charArrayS = s.toCharArray();
while (right < sLen) {
if (pattern[charArrayS[right]] > 0) {
text[charArrayS[right]]++;
if (text[charArrayS[right]] == pattern[charArrayS[right]]) {
count++;
}
}
right++;
while (count == distance) {
if (right - left == pLen) {
res.add(left);
}
if (pattern[charArrayS[left]] > 0) {
text[charArrayS[left]]--;
if (text[charArrayS[left]] < pattern[charArrayS[left]]) {
count--;
}
}
left++;
}
}
return res;
}
}
(本节完)