Sliding Window ✅¶

The author's earliest contact with sliding window is the Sliding Window Protocol, Sliding Window Protocol (Sliding Window Protocol), which is an application of the TCP protocol used for flow control during network data transmission to avoid congestion. The sender and receiver respectively have a window size of w1 and w2. The window size may vary according to changes in network traffic, but they are fixed in a simpler implementation. The window size must be greater than zero to perform any operations.

The sliding window in our algorithm is similar, except that it covers a wider range of situations. In fact, the above sliding window is a sliding window with a fixed window size at a certain moment, and the window size will also change as the network traffic and other factors change. Next we talk about the sliding window in the algorithm.

Introduction¶

Sliding window is an idea and method to solve problems, usually used to solve some continuous problems. For example, 209. Minimum Size Subarray Sum For more sliding window topics, please see topic list below.

Common routines¶

The sliding window is mainly used to deal with continuous problems. For example, if you solve the problem of "continuous substring xxxx" and "continuous subarray xxxx", you should think of a sliding window. Whether it can be solved or not, but this sensitivity still needs to be there.

In terms of types, there are mainly:

Fixed window size
The window size is not fixed, solve the largest window that satisfies the conditions
The window size is not fixed, solve the smallest window that satisfies the conditions (209. Minimum Size Subarray Sum belongs to this)

The latter two are collectively called variable windows. Of course, the basic idea is the same regardless of the type, and the only difference is the code details.

Fixed window size¶

For a fixed window, we only need to initialize the left and right pointers l and r, which represent the left and right vertices of the window respectively, and ensure that:

l is initialized to 0
Initialize r so that r-l + 1 is equal to the window size
Move l and r at the same time
Determine whether the continuous elements in the window meet the conditions defined by the title
4.1 If it is satisfied, then judge whether the optimal solution needs to be updated, and if necessary, update the optimal solution
4.2 If not satisfied, continue.

Variable window size¶

For variable windows, we also fixedly initialize the left and right pointers l and r, which represent the left and right vertices of the window respectively. The latter is different, we need to ensure:

Both l and r are initialized to 0
r pointer moves one step
Determine whether the continuous elements in the window meet the conditions defined by the title -3.1 If it is satisfied, then judge whether the optimal solution needs to be updated, and if necessary, update the optimal solution. And try to reduce the window size by moving the l pointer. Loop execution 3.1 -3.2 If not satisfied, continue.

To look at it visually, the r pointer keeps moving to the right, and the l pointer moves only after the window meets the conditions, which has the effect of window shrinkage.

Template code¶

Pseudo Code¶

Initialize slow pointer = 0
Initialize ans

for fast pointer in iterable collection
   Update the information in the window
   The while window does not meet the meaning of the question
      Expand or shrink the window
      Slow pointer movement
   Update answer
Return ans

Code¶

The following is the code for topic 209 and you can understand it.

C# Solution¶

using System;
using System.Linq;

namespace Algorithms.Medium
{
  public class MinimumSizeSubarraySum
  {
    public static int FindArrayLength(int[] nums, int target)
    {
      var l = 0;
      var total = 0;
      var ans = nums.Length + 1;

      foreach (var r in Enumerable.Range(0, nums.Length))
      {
        total += nums[r];
        while (total >= target)
        {
          ans = Math.Min(ans, r - l + 1);
          total -= nums[l];
          l++;
        }
      }

      return ans == nums.Length + 1 ? 0 : ans;
    }
  }
}

C# Tests¶

using Algorithms.Medium;
using Xunit;

namespace AlgorithmTests.Medium
{
  public class MinimumSizeSubarraySumTests
  {
    [Fact]
    public void FoundTest1()
    {
      Assert.Equal(2, MinimumSizeSubarraySum.FindArrayLength(new int[] { 2, 3, 1, 2, 4, 3 }, 7));
    }

    [Fact]
    public void FoundTest2()
    {
      Assert.Equal(1, MinimumSizeSubarraySum.FindArrayLength(new int[] { 1, 4, 4 }, 1));
    }

    [Fact]
    public void NotFoundTest1()
    {
      Assert.Equal(0, MinimumSizeSubarraySum.FindArrayLength(new int[] { 1, 1, 1, 1, 1, 1, 1, 1 }, 11));
    }
  }
}

List of questions (with solutions)¶

Some of the following topics have more direct information, and some of the topics are more hidden. You need to discover by yourself