• This article was first published on:Algorithmic Customs Clearance Manual
  • Text code address (welcomePainted “Star” 和 “Fork”) :Github.com/itcharge/Le…

1. Algorithm introduction

In the computer network, the Sliding Window Protocol is a measure of flow control in the transmission layer. The receiver controls the sending speed of the sender by notifying the size of the sender’s own Window, so as to prevent the sender from being overwhelmed by the sending speed. The sliding window algorithm we are going to describe uses the same properties.

Sliding Window: Maintains a Window of fixed or variable length on a given array/string. You can slide the window, zoom in and out, and maintain the optimal solution.

  • Sliding operation: the window can be moved in a certain direction. The most common is to move to the right.
  • Zoom operation: For a window of variable length, you can reduce the window length from the left, or increase the window length from the right.

The sliding window makes use of the fast and slow pointer technique in the double pointer. We can regard the sliding window as the interval between the fast and slow Pointers, or as a special form of the fast and slow Pointers.

2. Scope of application of sliding window

The sliding window algorithm is generally used to solve some problems of finding the properties (length, etc.) of continuous intervals that meet certain conditions. This algorithm can transform the nested loop in part of the problem into a single loop, so it can reduce the time complexity.

According to the problem, we can divide sliding Windows into the following two types:

  • Fixed length window: The window size is fixed.
  • Indefinite length window: Window size is not fixed.
    • Solve for the maximum window that satisfies the condition.
    • Find the smallest window that satisfies the condition.

Let’s talk about these two types of questions.

3. Fixed length window

3.1 Solving steps of fixed length window

Assume the fixed size of the window is WINDOW_size.

  1. Use two Pointersleft,right. The initial,left 、rightBoth refer to the first element of the sequence, namely:left = 0.right = 0The range of[left, right]It’s called a window.
  2. When the window is not reachedwindow_sizeWhen you’re big, you keep movingright,window_sizeFills the window with the element.
  3. When the window reacheswindow_sizeWhen the size is small, judge whether the continuous elements in the window meet the conditions specified in the question.
    1. If yes, then update the optimal solution according to the requirements.
    2. And then we move to the rightleft, thus reducing the window length, i.eleft += 1, so that the window size is alwayswindow_size.
  4. To the rightrightFills the window with elements.
  5. Repeat 2 to 4 steps untilrightAt the end of the sequence.

3.2 Fixed length window template

left = 0
right = 0

while right < len(nums):
    window.append(nums[right])
    
    # When the window size exceeds, shrink the window, the maintenance window is always window_size length
    if right - left + 1 >= window_size:
        #... Maintain the answer
        window.popleft()
        left += 1
    
    Enlarge the window to the right
    right += 1
Copy the code

Here is a concrete example of how to use sliding Windows of fixed size to solve the problem.

3.3 Number of subarrays of size K whose average value is greater than or equal to the threshold

3.3.1 Topic links

  • 1343. Number of subarrays of size K with an average value greater than or equal to the threshold – LeetCode

3.3.2 General idea of the topic

You are given an integer array arr and two integers k and threshold.

Requirement: Return the number of subarrays whose length is k and whose average value is greater than or equal to threshold.

3.3.3 Solution ideas

This problem is a typical fixed window size sliding window problem. The window size is K. Specific practices are as follows:

  1. ansUsed to maintain the number of answers.window_sumUsed to maintain the sum of elements in a window.
  2. left 、rightBoth refer to the first element of the sequence, namely:left = 0.right = 0.
  3. When the number of window elements is insufficientkKeep movingright,kFills the window with the element.
  4. When the number of window elements is zerok, i.e.,right - left + 1 >= k, judge whether the elements and average value in the window are greater than or equal to the threshold.
    1. If so, the number of answers + 1.
    2. And then we move to the rightleft, thus reducing the window length, i.eleft += 1, so that the window size is alwaysk.
  5. To the rightrightFills the window with elements.
  6. Repeat 3 to 5 steps untilrightIt reaches the end of the array.

Finally print the number of answers.

3.3.4 code

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) - >int:
        left = 0
        right = 0
        window_sum = 0
        ans = 0

        while right < len(arr):
            window_sum += arr[right]
            
            if right - left + 1 >= k:
                if window_sum >= k * threshold:
                    ans += 1
                window_sum -= arr[left]
                left += 1

            right += 1

        return ans
Copy the code

4. Indefinite length window

4.1 Solving steps of indefinite length window

  1. Use two Pointersleft,right. The initial,left,rightBoth refer to the first element of the sequence. That is:left = 0.right = 0The range of[left, right]It’s called a window.
  2. Add the rightmost element of the interval to the window, i.ewindow.add(s[right]).
  3. And then we move to the rightright, thus increasing the window length, i.eright += 1. Until the contiguous elements in the window meet the requirements.
  4. At this point, stop increasing the window size. Redirection constantly moves the left element out of the window, i.ewindow.popleft(s[left]).
  5. And then we move to the rightleft, thus reducing the window length, i.eleft += 1. Until the contiguous elements in the window no longer meet the requirements.
  6. Repeat 2 to 5 steps untilrightAt the end of the sequence.

4.2 Indefinite length Window template

left = 0
right = 0

while right < len(nums):
    window.append(nums[right])
    
    whileThe window needs to be shrunk:#... Maintainable answer
        window.popleft()
        left += 1
    
    Enlarge the window to the right
    right += 1
Copy the code

4.3 The oldest string without repeating characters

4.3.1 Topic links

  • 3. The largest string without repeating characters – LeetCode

4.3.2 General idea of the topic

Given a string s.

Requirement: Find the length of the longest string that does not contain repeating characters.

4.3.3 Solution ideas

Use a sliding window window to record the number of characters that are not repeated. Window is a hash table type.

Set two Pointers: left and right, respectively pointing to the left and right boundaries of the sliding window to ensure that there are no repeated characters in the window.

  • In the beginning,left,rightAll point to0.
  • Will the right most characters[right]Join current windowwindow, records the number of characters.
  • If the number of characters in the window is more than 1, that iswindow[s[right]] > 1, moves to the right continuouslyleft, reduce the length of the sliding window, and update the number of corresponding characters in the window untilwindow[s[right]] <= 1.
  • Maintains and updates the maximum string length without repeating characters. And then moves to the rightrightUntil theright >= len(nums)The end.
  • Output the maximum length of a string without repeating characters.

4.3.4 code

class Solution:
    def lengthOfLongestSubstring(self, s: str) - >int:
        left = 0
        right = 0
        window = dict()
        ans = 0

        while right < len(s):
            if s[right] not in window:
                window[s[right]] = 1
            else:
                window[s[right]] += 1

            while window[s[right]] > 1:
                window[s[left]] -= 1
                left += 1

            ans = max(ans, right - left + 1)
            right += 1

        return ans
Copy the code

4.4 The smallest subarray length

4.4.1 Topic Links

  • 209. Minimum length subarray – LeetCode

4.4.2 General idea of the topic

Given an array of only positive integers nums and a positive integer target.

Find the smallest contiguous subarray whose length is greater than or equal to target and return its length. If no subarray exists, return 0.

4.4.3 Solution idea

The most straightforward approach is violence enumeration, which is O(n2)O(n^2)O(n2). But we can use the sliding window method to solve the problem in the time complexity of O(n)O(n)O(n).

Set two Pointers: left and right, respectively pointing to the left and right boundaries of the sliding window. Ensure that the sum in the window is equal to or greater than target.

  • In the beginning,left,rightAll point to0.
  • To the rightright, adds the right-most element to the current window andwindow_sumIn the.
  • ifwindow_sum >= target, moves to the right continuouslyleft, reduce the sliding window length, and update the window sum to the minimum value untilwindow_sum < target.
  • And then we move to the rightrightUntil theright >= len(nums)The end.
  • Output window and the minimum value for the answer.

4.4.4 code

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) - >int:
        size = len(nums)
        ans = size + 1
        left = 0
        right = 0
        window_sum = 0

        while right < size:
            window_sum += nums[right]

            while window_sum >= target:
                ans = min(ans, right - left + 1)
                window_sum -= nums[left]
                left += 1

            right += 1

        return ans ifans ! = size +1 else 0
Copy the code

4.5 Subarrays whose product is less than K

4.5.1 Topic Links

  • 713. Subarrays whose product is less than K – LeetCode

4.5.2 Main idea of the topic

Given an array of positive integers nums and the integer k.

Find the number of contiguous subarrays whose product is less than k.

4.5.3 Solution idea

Slide window solution.

Set two Pointers: left and right, respectively pointing to the left and right boundaries of the sliding window, and ensure that the product of all numbers in the window window_product is less than K. Use window_product to record the product value in the window and count to record the number of subarrays that meet the requirement.

  • At the beginning, both left and right point to 0.

  • Add the rightmost element to the current subarray product WINDOW_product.

  • If window_product >= k, keep moving left to reduce the sliding window length, and update the current product value window_product until window_product < k.

  • Record the cumulative number of answers += 1 and move right until right >= len(nums) ends.

  • Output the cumulative number of answers.

4.5.4 code

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) - >int:
        if k <= 1:
            return 0

        size = len(nums)
        left = 0
        right = 0
        window_product = 1
        
        count = 0
        
        while right < size:
            window_product *= nums[right]

            while window_product >= k:
                window_product /= nums[left]
                left += 1

            count += (right - left + 1)
            right += 1
            
        return count
Copy the code

The resources

  • 【答案】 how does the sliding window of TCP protocol control flow? – zhihu
  • [Blogpost] Basic principles and Practice of sliding Window Algorithm – Huansky – Blogpark
  • Sliding Window – Lucifer. Ren