The sliding window algorithm is a more basic algorithm, which is generally the optimal solution of some regular array problems. That is to say, if an array problem can be solved by dynamic programming, but also can be solved by sliding Windows, then the sliding window is often more efficient.

The double pointer is not limited to the array problem, for example, the “fast and slow pointer” of the linked list scenario also belongs to the double pointer scenario. The sliding process of the fast and slow pointer itself will generate a window, for example, when the window shrinks to a certain extent, some conclusions can be obtained.

Therefore, it is very basic and important to master the sliding window. Next, I will introduce this algorithm according to my experience.

Intensive reading

Sliding Windows use double Pointers to solve the problem, so it is generally called double pointer algorithm, because two Pointers form a window.

When is it appropriate to use double Pointers? The general double pointer is the optimized version of the violence algorithm, so:

  1. If the problem is relatively simple and is an array or linked list problem, you can often try to see if double Pointers are solvable.
  2. If the array is regular, try double-pointers.
  3. If the linked list problem is more restrictive, such as requiring O(1) space complexity, only two-pointers may be solvable.

That is, when a problem is regular, or simple, or clever, try the two-pointer (sliding window) solution.

So let’s take an example. First of all, it’s the sum of two numbers.

The sum of two Numbers

The sum of two numbers is a simple problem, and actually has nothing to do with sliding Windows, but in order to introduce the sum of three numbers, let’s start with this problem. The title is as follows:

Given an integer array nums and an integer target value target, find the two integers in the array and the target value target and return their array subscripts.

You can assume that there is only one answer for each type of input. However, the same element in the array cannot be repeated in the answer.

The violent solution is to take the sum of all two numbers and find and end up as target, which is obviously a little slow, so let’s think about it another way.

Since we can swap space for time, and there are only two numbers, we can transform the problem by subtracting target from each numS term in a single iteration, and then finding the result that any of the following terms is equal to the preceding value, which means that they add up to target.

A hash table map can be used to speed up the query, that is, each item target-num is used as the key. If any subsequent num can be found in the map as the key, the solution is obtained, and the original value of the previous number can be stored in the map value. This is done only once, order n time.

The reason for this problem is that it is a single pointer, that is, only one pointer moves through the array, and it is solved quickly with a hash table. For slightly more complex problems, a single pointer is not enough, need to use a double pointer solution (generally do not use three or more Pointers), then the more complex problem is the sum of three numbers.

The sum of three number

The sum of three numbers is a medium problem, do not think that the sum of two numbers is only strengthened version, its train of thought is completely different. The title is as follows:

Given an array nums containing n integers, determine if there are three elements a, B, and c in nums such that a + b + c = 0. Please find all the triples that sum to 0 and are not repeated.

Since there are more than two numbers, it cannot be solved like a double pointer, because even if hash table storage is used, it will also encounter the “sum of two numbers” problem in traversal, and the hash table scheme cannot continue to be nested, that is, it cannot further reduce the complexity.

In order to reduce the time complexity, we hope that through only one array, the array will need to meet certain conditions we can use the sliding window, so we have to sort an array, use the fast line of time complexity is O (nlogn) time complexity, it is more than the sum of two Numbers, but because the topic is complex, the sacrifice is unable to avoid.

Assuming we sort from smallest to largest, we now have an incrementing array, and the classic sliding window method is available! How do I slide? Create two Pointers, called left and right, and let them slide between arrays. The size of the left and right window is exactly what the problem requires. When the slide is complete, return all the Windows that meet the requirements.

Then, for the general case, we take a global variable to store the sum of the current window numbers so that right+1 adds nums[right+1] and left +1 subtracts nums[left] to get a quick sum.

If nums[I] > 0, the array will be skipped, because the array is incremented, and the sum will always be greater than 0. Otherwise, the window sliding, first form three points [I, I +1, n-1], so keep I still, and keep the last two numbers, as long as their sum is greater than 0, the third point to the left (the number will become smaller), otherwise the second point to the right (the number will become larger), in fact, the second and third number is the sliding window.

In this case, the time complexity is O(n ^ 2), because there are two traversals, ignoring the smaller time complexity of quicksort.

What about the sum of four, the sum of five?

The sum of four number

This is exactly the same as the sum of three numbers, except for four.

So we sort again, and then we do double recursion, which is to make sure that the first two remain the same, and keep sandwiching the second two, which are I plus 1 and n minus 1, so it’s the same as the sum of the three, so the final time is O(n cubed).

So the sum of N numbers (N > 2) can be solved by this idea.

Why isn’t there a better way? I think it’s because:

  1. Regardless of the sum of numbers, the time complexity of quick sorting is fixed, so using the sum of three numbers actually takes advantage of the sorting algorithm.
  2. A sliding window can only be moved by two Pointers, but there is no window sliding algorithm with three Pointers that keeps the time complexity unchanged.

So for the sum of N numbers, after paying O(nlogn) time complexity through sorting, we can use the sliding window to optimize the time complexity of the two numbers to O(N), so the overall time complexity is O(n-2 + 1 N), that is, O(n-1 N), The smallest time complexity O(n²) is greater than O(nlogn), so the time complexity of quicksort is always ignored, so the sum of three is O(n²), the sum of four is O(n³), and so on.

It can be seen that we have crossed the threshold of sliding window from the simplest sum of two numbers to the sum of three numbers and the sum of four numbers. In essence, we make use of the ordered property of array after sorting, so that we can slide the window without going through the number group, which is the core idea of sliding window algorithm.

To reinforce this understanding, let’s look at a similar topic, the oldest string without repeating characters.

The oldest string without repeating characters

The oldest string without repeating characters is a medium problem with the following title:

Given a string, find the length of the smallest string that does not contain repeating characters.

Since the oldest string is continuous, it is obvious to consider the sliding window solution. In fact, after determining the sliding window solution, the problem is very simple, just Set left and right, and use a hash Set to record which elements exist, record the maximum length in the process, and try to move right. If repeated characters are found in the process of moving right, then left moves right. Until the duplicate character is eliminated.

It’s not that hard to figure out, but the question is, why is it that if you go through it once with a sliding window, it doesn’t leak? What if this is only order n?

Just think about two things:

  1. Since the substring is continuous, since there is no jump case, as long as a sliding window can contain all solutions, it covers all cases.
  2. What is not contained in a sliding window? As we will onlyrightMove to the right, and the attempt will be repeatedleftMove to the right after not repeating,rightAnd then we move to the right, and that ignores the repetition,rightLeft shift.

Obviously, if the four consecutive characters abcd do not repeat, then left does not repeat after moving right, so if you can move right to form bcDA window to continue searching, without trying BC, because this case is not repeated, But it’s definitely not optimal.

Ok, through this example, we can see that it is not difficult to reduce the scope of the sliding window, but more importantly, we should pay attention to the thinking behind why we can use the sliding window, whether the sliding window is neither heavy nor leaky. If we do not think clearly, the whole idea may be wrong.

So what about sliding Windows? Actually, no, we only mentioned the narrow window, which is a relatively single brain circuit. In fact, sliding Windows made up of double Pointers may not always slide normally. An interesting scene is fast and slow Pointers, which determines how the window slides with relative speed.

Classic topics on fast and slow Pointers include circular linked lists and removing duplicates from ordered arrays.

Circular linked list

Circular linked lists are a simple problem, with the following title:

Given a linked list, determine whether there are rings in the list.

If the order is not O(1), we can “contaminate” the original list a little during traversal and always find out if we have gone backwards.

But to require constant space overhead, we have to consider fast and slow Pointers. To tell the truth, when I first saw this problem, if I could think of a fast or slow pointer solution, it was absolutely very smart, because I had to have the ability to transfer knowledge. How do you migrate? Imagine the school is holding a sports meeting, I believe that every time there is a slowest student, slow to be chased by the fastest students.

Wait, isn’t a playground just a circular list? As long as someone runs slowly, will be run fast to catch up, catch up is not met? So the fast and slow Pointers run separately, as long as they meet, it is judged to be a circular linked list, otherwise it is not a circular linked list, and there must be a pointer to finish first.

So the minutiae is optimization efficiency, how slow is the slow pointer?

Some people say that a slow runner had better not run if he wants to be overtaken by a fast runner at a sports meeting. Yes, but in the circular linked list problem, the linked list is not a playground, maybe only a certain section is a ring, that is, the slow runner must at least run to the ring, then he can meet the fast runner, but the slow runner does not know where to start the ring, that is the difficulty.

Have you ever wondered why quicksort uses dichotomy instead of thirds? Why every time the middle to a knife, can be the fastest row? The reason is that dichotomy cuts the array to the smallest granularity with the smallest “depth”. So similarly, in the fast and slow hand, the slow hand might as well be half as fast as the fast hand in order to catch up with it as quickly as possible. So logically, why?

Intuitively, if the slow pointer is too slow, it may spend most of the time in the position before entering the ring. Although the fast pointer is fast, it always runs in the ring, so it is always unable to encounter the slow pointer. This gives us the enlightenment that the slow pointer can not be too slow; If the slow pointer is too fast, almost the same speed and fast pointer, like two athletes are mutually unmatched for the first, they really want to meet, estimated to run for several hours, so the slow pointer can not be too fast. So in this analysis, the slow pointer can only take half the speed in the middle.

But is it really possible to meet fastest at half the speed? Not necessarily. For example, if the linked list is a perfect circle and there are six nodes [1,6], then the slow pointer takes one step at a time and the fast pointer takes two steps at a time, then the total number of steps is 2,3,3,5, 4,1, 5,3,6,5,1,1. But what if the fast pointer takes three steps at a time? There are 2,4, 3,1, 4,4, 3 steps. So general speed is not necessarily optimal? No, the cost of node access is also taken into account when the computer addresses the linked list. Although the latter looks faster, it actually accesses next more times and is not as fast for the computer as the first one.

So it’s not exactly that the fast Pointers are twice as fast as the slow Pointers, but that the slow Pointers take one step at a time, and the fast Pointers take two steps at a time, because when they meet, the total number of moves is the least.

Again a simple problem, with the fast or slow pointer to determine the KTH node in the list or the list midpoint.

Determine the list midpoint

The fast pointer is twice as fast as the slow pointer. When the fast pointer reaches the tail, the position of the slow pointer is the middle point of the linked list.

The KTH last node in a linked list

The penultimate KTH node in the linked list is a simple problem, which is as follows:

Input a linked list, output the last KTH node of the list. In order to conform to the convention of most people, this case counts from 1, i.e. the last node of the list is the last node from the last.

If the slow pointer is k nodes slower than the fast pointer, when the fast pointer reaches the end, the slow pointer will point to the last k+1 node. Just count this one carefully and don’t make any mistakes.

Finally, another classic use of fast and slow Pointers is to remove duplicates from an ordered array.

Removes duplicates from an ordered array

Delete duplicates from an ordered array

Give you an ordered array nums, ask you to delete the repeated elements in place, so that each element appears only once, return the deleted array after the new length.

In this case, to remove duplicate elements in place and return the length, only fast or slow Pointers can be used. But how? How fast and how slow?

In fact, this question is not as fast or slow as the previous question preset, but based on the actual numbers encountered to judge.

We’re going to assume that the slow pointer is slow and the fast pointer is fast, and notice that the variable naming is interesting, and this is the same two-pointer problem, either slow right or slow fast, but it’s all about how you move the pointer.

As long as we let FAST scan the complete table, move all the non-repeat together, so the time complexity is O(n), the specific approach is:

  1. letslow 和 fastThey all start out pointing to index 0.
  2. Because it isOrderly array, so even if there is repetition, it must be connected together, so we can letfastScan straight back, only to find andslowDifferent values, and then the sumslow+1Swap, and thenslowIncrement, keep recursing untilfastWe end up at the end of the array.

Once you’ve done this, the subscript of slow is the answer.

If fast has the same value as slow, then slow will wait, because the same value will be ignored. To let fast go is to skip repeated values.

Having said the common usage of double pointer, let’s look at some special problems that are more difficult to bite, here we mainly talk about two, respectively is the container that holds the most water and receive rain water.

The container that holds the most water

The container that holds the most water is an intermediate question, with the following questions:

Give you n non-negative integers A1, A2… Each number represents a point in the coordinates (I, ai). Draw n vertical lines in the coordinates, and the two endpoints of vertical line I are (I, AI) and (I, 0). Find the two lines that together with the X-axis will hold the most water.

I suggest that you read the topic carefully before continuing. This topic is relatively complex.

All right, why is this a two-pointer problem? Because how do we calculate the volume of water? So this problem just simplifies to length times width.

The length is the distance between the two columns selected, and the width is the height of the shortest column. The problem is that although the farther apart the columns are, the larger the length is, the width is not necessarily the largest, and the optimal solution cannot be identified at a glance.

So you still have to try it multiple times, so how can you use the least number of times, but not lose? Define two left and right Pointers, pointing to 0 and n-1 respectively, i.e., the first and the last two positions. At this point, the length is the maximum (the distance between the pillars is the furthest).

  • The longer one? If the new shorter one is shorter, then the width is shorter; It doesn’t matter if the new one is shorter and longer, because the shorter one determines the water level.
  • The shorter one? If the new one is longer, there is a chance it will be bigger overall.

So we move the shorter one, and we calculate the volume each time, and we end up when the two columns meet, and the maximum volume in the process is the global maximum volume.

Different from the above common questions, the focus is not on whether the sliding window algorithm can be used, but whether the rules of moving the pointer can be found.

And of course you might say, well, why should two Pointers be defined at the very end, and not somewhere else? Because then you can’t control the variables.

If the pointer is in the middle, the spacing of the columns changes at the same time as the length of the column as the pointer moves outward, making it difficult to find a perfect path. If we move the shorter column, for example, because the shorter column determines the lowest water level, changing it might make the lowest water level higher, but the problem is that the distance between the two columns is also increasing, so it’s not clear whether it’s better to move the shorter column or the longer column.

To be honest, this method is not easy to think of, you need to find a few more options to try to discover. Of course, algorithms are easier to follow if they can be derived from a set set of rules, so accept these mental leaps.

Now let’s look at a more specific sliding window problem, which even breaks down into multiple sliding Windows.

After the rain

Catching rain is a difficult problem. The questions are as follows:

Given n non-negative integers to represent the height diagram of each column of width 1, calculate how much rain the columns in this order can catch after rain.

Instead of rainwater harvesting, we’re looking at the whole thing, and we’re trying to figure out how much water we can catch.

Actually, this one is a little bit easier to start with than the last one, because we can do it from left to right. After thinking, it is found that only when a “groove” is produced can rainwater be received, and the groove is determined by the highest pillars on both sides of it. Then what range is a groove?

Obviously the grooves can be grouped explicitly, and a groove can’t be divided into multiple grooves, just like when you look at puddles, no matter how many and how deep the puddles are, they can always be counted clearly, so we’ll start counting from left to right.

How do I count the grooves? Using the sliding window method, each window is a groove, so the starting point of the window left is the first column on the left, there is the following situation:

  • If the column directly adjacent to the right is taller (or the same height), there is no way to catch rainwater from it looking to the right, so just discard it,left++.
  • If the column directly adjacent to the right is shorter, there is an opportunity to create grooves.
    • So if you keep looking to the right, if the right is always shorter, you can’t catch the rain.
    • If there is a taller one on the right, it can catch the rain. The question is how much to catch, and where to find the end?
      • As long as the height of the leftmost column is recorded, the right column ends with the condition “meet a column as high as the leftmost column”, because how much water a groove can hold depends on the shortest column. Of course, if there are no columns on the right, even though it is lower than the left, as long as it is higher than the deepest, it also counts as a finishing point.

In this problem, once the end of the groove is reached, the left is updated to start a new round of groove calculation, so there are multiple sliding Windows. It can be seen from this question that the sliding window question type is quite flexible. Not only the judgment conditions vary from question to question, but also the number of Windows may be multiple.

conclusion

The essence of sliding window is the double pointer play, different topics have different routines, from the simplest in accordance with the law of the double, to the fast and slow Pointers, and then to the special algorithm for different topics without fixed routines.

In fact, the routine of regular inclusion belongs to the category of collision Pointers. Generally, the sorted array can be judged step by step, or judged by dichotomy. In short, it is not judged according to the overall traversal, so the efficiency is naturally high.

Fast and slow Pointers also have routines to follow, but the specific number of fast, or slow, may be specific to see the scene.

For sliding Windows with no set routines, you have to taste the problem carefully. If all routines can be summarized, the algorithm will be less fun.

The discussion address is: close reading algorithm-Sliding Windows · Issue #328 · dT-fe /weekly

If you’d like to participate in the discussion, pleaseClick here to, with a new theme every week, released on weekends or Mondays. Front end Intensive Reading – Helps you filter the right content.

Pay attention to the front end of intensive reading wechat public account

Copyright Notice: Freely reproduced – Non-commercial – Non-derivative – Remain signed (Creative Commons 3.0 License)