This is the sixth day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

Earlier, I talked about a sliding window idea called “Maximum string without repeating characters.”

Juejin. Cn/post / 702711…

Today, I’m going to try to summarize some common solutions for these kinds of problems

The sliding window

What is a sliding window?

Slide: refers to the window is moving, in a certain direction to move

Window: refers to a range, which can be fixed or variable

The instance

There are two common examples of the sliding window idea

  • The sliding window protocol of TCP is used for traffic control during network data transmission to avoid congestion
  • Flow limiting algorithm, sliding window flow limiting, a certain period of time to allow for small window flow limiting

Algorithm subject

There are a lot of sliding window problems, generally divided into the following several

  1. The oldest string without repeating characters
  2. A substring that concatenates all the words
  3. Minimum coverage substring
  4. The largest string containing at most two distinct characters
  5. Smallest subarray of length
  6. Maximum sliding window
  7. String arrangement
  8. The minimum interval
  9. Minimum window subsequence

In common

The commonality of these questions is that they are monotonic. As the left pointer increases, the optimal right pointer remains monotonic

With this property, it is possible to solve problems using the general template of the sliding window algorithm

To continue with yesterday’s question [longest string without repeating characters] :

  1. We initialize left = right = 0 in string S using the left and right pointer technique in double Pointers, calling the index closed interval [left, right] a “window”.
  2. We first enlarge the window [left, right] by increasing the pointer to right until the string in the window does not meet the requirements (contains duplicate strings).
  3. At this point, we stop adding right, and instead keep adding left Pointers to shrink the window [left, right] until the string in the window meets the requirement (no duplicate strings). At the same time, we need to update the result each time before adding left, and record whether the current substring length is greater than the oldest string length, if so, record the longest string length.
  4. Repeat steps 2 and 3 until the right pointer reaches the end of the string S.

A typical scenario

1. Array or string, contiguous, the result that needs to be output or compared is contiguous in the original data structure (contiguous in string does not repeat substring, contiguous elements in array maximum sum)

2, double needle, every time sliding window, only observe element changes on both ends of the window, the window within the elements of integrity, sliding window can only by operating the heads of two position changes, but compare the results often want to use all elements in the window (check window contains repeated characters, contrast and window elements)

The problem solving template

Template is actually some pseudo-code implementation, specific problems and then specific analysis optimization, flexible

Variable length sliding window

The window container holds elements in the window. You can use arrays, hashsets, hashmaps, etc
window window;
// Save the best result, maximum or minimum, etc
result = defaltvalue;
// Construct window left and right boundary Pointers
int left = 0, right = 0;

while(right < s.size()) {
    window.add(s[right]);
    // Determine the appropriate position, perform the right pointer move, not necessarily here
    right++;
    // If the window is completed, move left to narrow the window
    while(Window meets the requirement) {// If the window conditions are better, update result
        result = maxOrMin(result, window);
        // Remove the left pointer elementwindow.remove(s[left]); left++; }}return result;
Copy the code

Fixed length sliding window:

// Set window size to k
string s;
// Find the maximum number of vowels in s when the window size is k
int right = 0; 
while(right < s.size()) {
    window.add(s[right]);
    right++;
    // Window construction is complete.
    if (right>=k) {
        // This is already a window, do something according to the condition
        / /... You can calculate the maximum window value and so on
        // Finally, don't forget to remove the right-k element from the window}}return result;    
Copy the code

chestnut

Given an array of n positive integers and a positive integer target.

Find the smallest contiguous subarray [numsl, numSL +1,…, numsr-1, numsr] that satisfies the sum and ≥ target, and return its length. If no subarray exists, return 0.

Example 1:

Input: target = 7, nums = [2,3,1,2,4,3] output: 2 description: the subarray [4,3] is the smallest subarray in this condition. Example 2:

Input: target = 4, nums = [1,4,4]

Input: target = 11, nums = [1,1,1,1,1,1,1,1] output: 0

1. Firstly, analyze whether it conforms to the definition of sliding window algorithm

Array, minimum continuous, and so on. It’s easy to think of a sliding window with variable length

2. Use the template method to solve the problem

Implementation:

You don’t need to store the original elements in the window, you just need to keep the sum in the window

public int minSubArrayLen(int target, int[] nums) {
    // Keep the sum of the elements in the window
    int sum = 0;
    // Shortest path
    int minLength = Integer.MAX_VALUE;;
    int left =0, right =0;

    while(right < nums.length){
        sum += nums[right];
        // If the condition is met, we need to control the left pointer movement
        while(sum >= target){
            minLength = Math.min(minLength, right-left + 1);
            sum-=nums[left];
            left++;
        }
        right ++ ;
    }

    return minLength == Integer.MAX_VALUE? 0: minLength;
}
Copy the code

summary

Summary problem solving template can be more clear when doing problems, but it can not be copied mechanically. Only by making corresponding optimization choices according to the actual topic can the algorithm be more efficient, but it still needs more practice and more thinking.