I. Application Scenarios
Sliding window is suitable for continuous subsequence problems, continuous is the key word, once you see in the description of the subsequence can be discontinuous, then you can boldly exclude the sliding window method, force button on the common examples of some questions the longest does not contain repeated letters of the subsequence, the minimum coverage substring and other problems.
Use two.
The code of the sliding window is compared with the template. The subscript I and j are used to record the left and right boundaries of the sliding window, and then the following questions need to be clear. When the sliding window needs to be larger, that is, the right boundary needs to be extended to the right, and what data needs to be updated when it needs to be extended to the right. When the sliding window needs to stop growing, that is, the right boundary needs to stop extending to the right. When the sliding window needs to shrink, that is, the left edge needs to shrink to the right, and what data needs to be updated when it shrinks to the right.
Three examples.
Let’s start with a simple example to practice.
When a window contains characters to be read, the description repeats, the window begins to shrink, the left edge begins to move to the right,
If the window does not contain characters to be read, it is not repeated. The window continues to expand, and the right boundary continues to move to the right. Each expansion is recorded.
As you can see, this problem often requires us to determine whether or not to repeat, so common methods to determine whether or not to repeat are arrays and hashsets.
Arrays are good for small numbers of elements that can be easily converted to subscripts. For example, if the element has only 26 letters, the subscripts can be obtained by – ‘a’, but the s is not just letters, so use HashSet instead.
class Solution {
public int lengthOfLongestSubstring(String s) {
if (s==null) {return -1;
}
HashSet<Character> set=new HashSet<>();
int i=0;/ / the left border
int j=0;/ / right border
int len=s.length();
char[] chars=s.toCharArray();
int res=0;
while (j<len){
while (set.contains(chars[j])){
// Repetitions shrink
set.remove(chars[i]);
i++;
}
set.add(chars[j]);
j++;
res=Math.max(res,j-i);
}
returnres; }}Copy the codeLet’s take a harder but more standard sliding window example.
Minimum coverage from the string, difficult questions, good guy, difficult questions is I can think, now I dare to think about difficult questions, then I want to do what difficult questions I dare not think.
Anyway, this problem is relatively easy to analyze. Because the subject needs to return a t cover all characters of the shortest string, so we need to start to use field records the substring starting subscript, in addition, because the topic request is the shortest, so we still need a len value records at the moment t cover all characters of the length of the shortest string, once have new conform to the requirements of the subject of a substring occurs in a string, You need to compare the length of the new string to len, and if len is larger, update len to the length of the new substring, as well as update left. When the slide window does not contain all characters of the string T, the slide window expands and the right boundary moves to the right. When the sliding window contains all characters of the string T, the sliding window shrinks and the left boundary moves to the right. Every time the sliding window shrinks, a comparison is made. The specific comparison can be seen above and will not be described here. The final code is shown below.
class Solution {
public String minWindow(String s, String t) {
if (s==null||t==null) {return new String();
}
HashMap<Character,Integer> need=new HashMap<>();// Record the number of letters in the substring to be overridden
HashMap<Character,Integer> window=new HashMap<>();// Record the number of letters in the window containing substrings
char[] sChar=s.toCharArray();
char[] tChar=t.toCharArray();
for (char c:tChar){
need.put(c,need.getOrDefault(c,0) +1);
}
int left=0,right=0,start=0,valid=0,len=Integer.MAX_VALUE;
// Valid indicates the number of substring letter types contained in the window
while (right<sChar.length){
char rChar=sChar[right];
right++;
if (need.containsKey(rChar)){
window.put(rChar,window.getOrDefault(rChar,0) +1);
if(window.get(rChar).equals(need.get(rChar))){ valid++; }}while (valid==need.size()){
// The window contains all letters of the substring and begins to shrink
if (right-left<len){
len=right-left;
start=left;
}
char lChar=sChar[left];
left++;
if (need.containsKey(lChar)){
if (window.get(lChar).equals(need.get(lChar))){
valid--;
}
window.put(lChar,window.get(lChar)-1); }}}return len==Integer.MAX_VALUE ? "":newString(sChar,start,len); }}Copy the code4. Wrong demonstration
As mentioned before, when I see a problem that requires a continuous subsequence, I can think in the direction of the sliding window. So when I see the problem below, I unconsciously think in the direction of the sliding window.
Continuous subsequence, fit.
When the number of left and right parentheses in the window is equal, it determines whether the parentheses are valid and records the length.
The window should shrink when there are more close parentheses than open parentheses.
If the number of open parentheses is greater than the number of close parentheses, the window should continue to expand to the right.
Well, a set of analysis down to make sense, I was really smart, pow, soon, I wrote the following code out
class Solution {
public int longestValidParentheses(String s) {
if (s==null) {return -1;
}
int lK=0;// The number of left parentheses
int rK=0;
int len=s.length();
int left=0;// Window left margin
int right=0;
int res=0;
char[] sChar=s.toCharArray();
while (right<len){
if (sChar[right]=='('){
lK++;
}else {
rK++;
}
right++;
if (lK==rK&&isValid(sChar,left,right)){
res=Math.max(res,right-left);
}
while (lK<rK){
if (sChar[left]=='('){
lK--;
}else{ rK--; } left++; }} ` ` `return res;
}
private boolean isValid(char[] chars,int i,int j){
// Check whether the parentheses are valid}}Copy the codeAs soon as I saw that the code had passed the three test cases given by the topic, I submitted it decisively. Indeed, it was a fierce operation like a tiger, and a look at the result was zero bars and five.
Cold analysis.
Missing one case, when the number of open parentheses is greater than the number of close parentheses, there are actually two possibilities. The first case is when there are too many left parentheses and you need to shrink the window. The second case is when the number of closing parentheses is low, and you need to expand the window to the right. I only considered the second case, not the first case, at this time there may be a smart friend to ask, so you take the first case into account, don’t you? That’s true in theory, but as I mentioned earlier, when there are more close parentheses than open parentheses, the window will also shrink, so it will shrink as long as the left and right parentheses are not equal, and equality is valid, which is not true, just take a random use case.
Case: "()"Copy the codeThe longest valid parenthesis above is 2, but the result would be 0 if calculated using the above method. It can be found that the problem of forcibly applying sliding Windows to the above problems is that the conditions for shrinking or expanding the window are not unique, so when this happens, you can give up using sliding Windows. This problem should be solved by dynamic programming, but it is not the focus of this article.
The resources
1. L. Book (due to the controversy over plagiarism of the reference materials, the full name will not be used)