preface

This is not a series that gives you a problem and tells you how to solve it, but rather an article that categorizes a series of problems, finds out how to solve them, and comes up with a general framework code. It is much more useful to know how to solve a series of problems than to know how to solve a single problem, because you will always have problems that are not brushed.

The body of the

You should be familiar with the sliding window, in the TCP protocol has this concept, used to control network traffic, avoid congestion.

This idea is similar in the algorithm, which is mostly used to solve the problem of finding conditions in a continuous interval, for example, given a string, finding the longest string without repeating characters. This idea is mainly applied to array and string data structures.

The sample

The main idea of sliding window is to maintain a pair of Pointers, and move the right pointer to expand the window size under certain conditions until the solution in the window does not meet the problem meaning. At this time, we need to move the left pointer according to the situation, repeatedly move the left and right Pointers and solve the problem in the interval until the double pointer can no longer move.

For example, it is very convenient to solve the problem according to the above ideas:

var lengthOfLongestSubstring = function(s) {
    // Used to store values during pointer movement
    let map = {}
    / / double pointer
    let left = 0
    let right = 0
    / / the result
    let count = 0
    // End condition of pointer movement
    while (right < s.length) {
        const char = s[right]
        // According to the problem we need to find the longest string that does not repeat
        // When a char appears we need to move the left pointer to the next bit of the repeated character
        if (char in map) {
            left = Math.max(left, map[char] + 1)}/ / to solve
        count = Math.max(count, right - left + 1)
        // Move the right pointer and place the index
        map[char] = right++
    }
    return count
};
Copy the code

This topic is high frequency question, we must grasp

The framework

According to the above problem, we can get a pseudo code of the general framework of sliding window solution,

let left = 0
let right = 0
while(right < size) {get current index data right++ data update, etcwhile{left++ data removal, etc.}}Copy the code

Here are a few things that need to change in the framework:

  • Update of data after the right pointer is moved right
  • Determine when the window needs to shrink
  • Update of data after moving the left pointer to the right
  • So let’s figure out the best solution

Let’s try to solve a few problems based on the framework code.

In actual combat

209. Smallest subarray of length

Answer:

  1. Move the right pointer and store the sum of the moved values
  2. When the sum is greater thansWhen moving the left pointer to narrow the window, we need to update the accumulated value and the solution we need
var minSubArrayLen = function(s, nums) {
    // Define a double pointer
    let left = 0
    let right = 0
    // Find the required variables
    let length = Infinity
    let sum = 0
    // End condition of pointer movement
    while (right < nums.length) {
        // Get the current index data
        sum += nums[right]
        // Narrow the window condition
        while (sum >= s) {
            / / to solve
            length = Math.min(length, right - left + 1)
            // Zoom out
            sum -= nums[left++]
        }
        // Expand the window
        right++
    }
    return length === Infinity ? 0 : length
};
Copy the code

This is Leetcode 209, and the answer is basically the framework code, except for a few minor tweaks. You can continue to follow this idea to solve the following problems, and quickly master the routine of solving problems through sliding Windows.

438. Find all letter heterotopic words in the string

Answer:

  1. Stored by hash tablepThe number of occurrences of a character in
  2. Moves the right pointer to determine if the current character still qualifies
  3. If the condition is not met, move the left pointer to shrink the window, and the hash table needs to be updated
  4. If the current character does not exist in the hash table, the double pointer can be skipped to the next digit
var findAnagrams = function(s, p) {
    if(! s.length || ! p.length || s.length < p.length)return []
    // Find the required variables
    const map = {}
    const result = []
    // Define a double pointer
    let left = 0, right = 0
    // Hash the characters in string p
    for (let i = 0; i < p.length; i++) {
        const char = p[i]
        if(! (charin map)) {
            map[char] = 0
        }
        map[char] += 1
    }
    // End condition of pointer movement
    while (right < s.length) {
        const char = s[right]
        // Move the right pointer if there are characters in map
        if (map[char] > 0) {
            map[char] -= 1
            right++
        // Otherwise check whether the character pointed to by the left pointer exists in the map
        } else if (map[s[left]] >= 0) {
            map[s[left]] += 1
            left++
        // If not, move all the left and right Pointers to next
        } else {
            left = right += 1
        }
        // Store the correct solution
        if (right - left === p.length) {
            result.push(left)
        }
    }
    return result
};
Copy the code

76. Minimum coverage substring

Find all letter heterotopic words in a string

  1. Stored by hash tabletThe number of occurrences of a character in
  2. Moves the right pointer to determine if the current character still qualifies
  3. If the condition is not met, move the left pointer to shrink the window, and the hash table needs to be updated
var minWindow = function(s, t) {
    // Define a double pointer
    let left = 0, right = 0
    // Find the required variables
    let length = Infinity
    let map = {}
    // Update match when it encounters characters in t. Note that characters in T may appear multiple times in s
    // Therefore, it is not necessary to update the match every time
    let match = 0
    // Record the start position of the shortest substring
    let start = 0
    // Hash the characters in string t
    for (let i = 0; i < t.length; i++) {
        const char = t[i]
        if(! (charin map)) {
            map[char] = 0
        }
        map[char] += 1
    }
    // End condition of pointer movement
    while (right < s.length) {
        const char = s[right]
        // Update data when the right pointer moves
        if (char in map) {
            map[char] -= 1
            if (map[char] >= 0) match += 1
        }
        // Narrow the window condition
        while (match === t.length) {
            // Find a better solution, save the data
            if (length > right - left + 1) {
                length = right - left + 1
                start = left
            }
            // Move the left pointer and update the data
            const char = s[left++]
            if (char in map) {
                if (map[char] === 0) match -= 1
                map[char] += 1}}// Move the right pointer
        right++
    }
    return length === Infinity ? ' ' : s.substring(start, start + length)
};
Copy the code

conclusion

After the previous exercises, you should be able to see that the sliding window idea is mostly used to solve the problem of array and string neutron elements.