Sliding window problem summary

When you first touch the sliding window , You may feel like you can't do it , But after doing more related topics , You can sort out a set of frames , It is not particularly difficult to figure out the problem of sliding window after routine .
It should be noted that , Sliding windows include fixed length and non fixed length windows , There are differences in some details .

One 、643. Maximum average of subarrays I

Answer key

This problem is essentially a sliding fixed window problem , Define two pointers left,right They are the left and right boundaries of the window . When right-left+1==k when , Window formation , If more than k Then the left border goes forward . The average value is calculated only when the window is formed .

Code

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
            if not nums or not k:
                return 0

            sum = 0
            max_average = -float('inf')
            left,right = 0,0
            #  create a window 
            while right < len(nums):
                sum += nums[right]
                #  Determine whether the window has been created , If the window has been formed , Just calculate the average 
                if right-left+1 == k:
                    average = sum/k
                    max_average = max(max_average,average)
                #  When the range of the window is exceeded ,left The pointer narrows down 
                if right-left+1 >= k:
                    sum -= nums[left]
                    left += 1
                right += 1

            return max_average

Two 、3. Longest substring without repeating characters

Answer key

The sliding window problem can be viewed as a queue , The feature of queues is FIFO
When the window is full or does not meet the requirements , Should be out of the team , That is, operate the left side of the original sequence .

Code

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
            if not s:
                return 0
            max_count = 0

            que = []
            #  Traverse the entire sequence 
            for right in range(len(s)):
                #  If you are already in the queue , Just go out of the team 
                while s[right] in que and que:
                    que.pop(0)
                #  Otherwise, join the team 
                que.append(s[right])
                #  Returns the maximum length 
                max_count = max(max_count,len(que))

            return max_count

3、 ... and 、209. Subarray with the smallest length

Answer key

The title is very clear , Continuous subarray , Isn't this a sliding window ？ For sliding windows , Move first right, Until it doesn't meet the conditions , Move again left

Code

def minSubArrayLen(nums,target):
    if not target and not nums:
        return 0
    sum = 0
    res = float('inf')
    left,right = 0,0 #  The left and right borders of the window 
    while right < len(nums):
        sum += nums[right]
        while sum >= target:
            subLength = right-left+1 #  The length of the window 
            res = min(subLength,res)
            sum -= nums[left]
            left += 1
        right += 1

    return res

Four 、1456. The maximum number of vowels in a fixed length substring

Answer key

Slide the window , Also create a new function to judge whether it is a vowel letter

Code

'''  Sliding window problem , It's a relatively simple topic  '''
class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        def isYuan(s):
            if s=='a' or s=='e' or s=='i'or s=='o'or s=='u':
                return 1
            else:
                return 0
        
        count = 0
        max_num = 0

        if not s or not k:
            return 0

        right = 0
        while right<len(s):
            #  Traverse backward one by one , Judge whether it is a vowel 
            count += isYuan(s[right])
            right += 1
            #  The window has been formed , If you want to judge again , Must be removed from the front of the window 
            if right>=k:
                #  Update the maximum length that meets the requirements 
                max_num = max(max_num,count)
                #  The window size is fixed , One must be taken out first , Can be inserted 
                count -= isYuan(s[right-k])

        return max_num

Code 2 , I feel this is easy to understand , A little more vivid

'''  Sliding window problem , It's a relatively simple topic  '''
class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        def isYuan(s):
            if s=='a' or s=='e' or s=='i'or s=='o'or s=='u':
                return 1
            else:
                return 0
        
        count = 0 #  The number of vowels in the window 
        max_count = 0 #  The number of the most vowel letters 

        left,right = 0,0
        while right <len(s):

            count += isYuan(s[right])

            if right-left+1 == k:
                max_count = max(max_count,count)
            right += 1
            if right-left+1 > k:
                count -= isYuan(s[left])
                left += 1


        return max_count

5、 ... and 、1695. Delete the maximum score of the subarray

It seems that I really have to learn Chinese well , This topic is confused, but I don't understand what it means , Read the comment area to understand .
Here's an array of positive integers nums , Find the cumulative sum of the largest continuous subarray of non repeating elements , Returns the value of its cumulative sum .

Answer key

Use queues to solve this problem , Just traverse to a new element , This element will definitely join the team , And if this element already exists in the team , Then he has been out of the team , Until there is no repeating element in the team .

Code

''' Here's an array of positive integers  nums , Find the cumulative sum of the largest continuous subarray of non repeating elements , Returns the value of its cumulative sum .'''
class Solution:
    def maximumUniqueSubarray(self, nums: List[int]) -> int:
        res = 0
        que = collections.deque()
        maxN = 0
        for i in range(len(nums)):
            maxN += nums[i]
            #  If there is this number in the queue , Then all the people in front of them will be out of the team 
            while nums[i] in que:
                temp = que.popleft()
                maxN -= temp
            
            que.append(nums[i])
            res = max(maxN, res)
        return res

6、 ... and 、438. Find all alphabetic words in the string

Answer key

Personally, I think this problem is relatively difficult in the sliding window problem , This is a sliding window , The size of the window is p The length of .
Because the title has already said , It's all small letters , So you can create a new one with a length of 26 Array of , This array is used to store which letter has appeared and how many times . Of course , The values in the array , Is the element relative to the letter a Relative position of . This relative position can be determined by ord() To achieve .
If you don't understand while loop , You have to be yourself debug It can be realized by hand .

Code

def findAnagrams_re(s,p):
    m,n = len(s),len(p)
    if n>m:
        return None
    s_cnt = [0]*26
    p_cnt = [0]*26
    res = []
    #  Yes p_cnt To initialize 
    for i in range(n):
        p_cnt[ord(p[i])-ord('a')] += 1
    left = 0
    #  Traverse s Array 
    for right in range(m):
        cur_right = ord(s[right])-ord('a')
        s_cnt[cur_right] += 1
        #  If this letter is in p There has never been , Or in s The number of occurrences in is greater than that in p Is the number of times , Move left window 
        while s_cnt[cur_right]>p_cnt[cur_right]:
            cur_left = ord(s[left])-ord('a')
            s_cnt[cur_left] -= 1
            left += 1
        #  If the window forms , Then add the left boundary to res in 
        if right-left+1 == n:
            res.append(left)
    return res

7、 ... and 、567. Arrangement of strings

This topic is exactly the same as the one above .

Answer key

Not much , If there is a qualified window , Go straight back True Just fine .

Code

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
            if not s1 or not s2:
                return False
            m,n = len(s1),len(s2)
            if n<m:
                return False
            s1_cnt = [0]*26
            s2_cnt = [0]*26

            for i in range(m):
                s1_cnt[ord(s1[i])-ord('a')] += 1

            left = 0
            for right in range(n):
                cur_right = ord(s2[right])-ord('a')
                s2_cnt[cur_right] += 1

                while s2_cnt[cur_right]>s1_cnt[cur_right]:
                    cur_left = ord(s2[left])-ord('a')
                    s2_cnt[cur_left] -= 1
                    left += 1

                if right-left+1 == m:
                    return True

            return False

8、 ... and 、1004. Maximum continuous 1 The number of III

This topic is really good , I think it's very interesting . In fact, I couldn't think of ideas at the beginning , After reading others' ideas, I feel suddenly enlightened .

Answer key

Or the old method of sliding windows , Since it's the window , You have to have left and right boundaries , namely left,right. What other parameters are used to define . Definition zeros In the record window 0 The number of , When zeros>k when , The left edge of the window moves .

Code

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
            if not nums:
                return None

            left = 0
            max_count = 0
            zeros = 0
            #  Traversal array 
            for right in range(len(nums)):
                if nums[right]==0:
                    zeros += 1
                #  Move left border 
                while zeros>k:
                    if nums[left]==0:
                        zeros -= 1
                    left += 1
                #  Return results 
                max_count = max(max_count,right-left+1)
                
            return max_count

Nine 、1052. Angry Bookstore owners

The title description is problematic ,customers[i] In the first i The number of customers entering the store at the beginning of the minute , Not number . You can view the English description .

Answer key

The first solution
1. We can add satisfied customers to the answer first , At the same time, the corresponding customers[i] Set as 0.
2. Then the question turns into ： stay customers A continuous section with a length of minutes Subarray , Make the sum maximum .
At that time, I saw this solution , It's amazing , It seems that I am still blocked and long on the way of Algorithm

The second solution
This solution is a popular solution for sliding windows , I guess I read the above topic , This should also be clear . Just add more if Sentence judgment .

Code

class Solution:
    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:
        sum_ = 0
        for i in range(len(customers)):
            if grumpy[i] == 0:
                sum_ += customers[i]
                customers[i] = 0 #  Remember to set it to 0

        max_,cur = 0 ,0
        for i in range(len(customers)):
            cur += customers[i]
            if i >= minutes:
                cur -= customers[i-minutes]

            max_ = max(cur,max_)

        return sum_ + max_

class Solution:
    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:
         #  The total number of customers in all the time when they are not angry 
        sum_ = 0
        for i in range(len(customers)):
            if grumpy[i] == 0:
                sum_ += customers[i]
        #  Angry time interval , How many customers will be dissatisfied 
        cur_value = 0
        #  First calculate the starting interval 
        for i in range(minutes):
            if grumpy[i] == 1:
                cur_value += customers[i]

        #  The maximum value of dissatisfied customers 
        res_value = cur_value
        for i in range(minutes,len(customers)):
            if grumpy[i]==1:
                cur_value += customers[i]
            if grumpy[i-minutes]==1:
                cur_value -= customers[i-minutes]

            res_value = max(res_value,cur_value)

        return sum_ + res_value

Ten 、1423. The maximum number of points available

There is one saying. , I also think the idea of this topic is great

Answer key

Let's find the maximum number of points we can get , It may be difficult to relate to the sliding window problem at first , How to use sliding window to operate from both sides . In fact, this topic changes , You can definitely think of a solution immediately , Let you find the value and the minimum interval in a fixed length window . Finally, subtract the smallest from the sum to get the answer we want .

Code

'''  Find a length of window_size The minimum interval of , Just subtract again  '''
class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        n = len(cardPoints)
        window_size = n-k #  Window size 
        left,right,sum_ = 0,0,0
        min_value = float('inf') #  The smallest window and 
        window_value = 0 #  Window value 

        while right<n:
            sum_ += cardPoints[right] #  All sums in the array 
            window_value += cardPoints[right]
            #  If the window length is exceeded , Move left boundary back 
            if right-left+1 > window_size:
                window_value -= cardPoints[left]
                left += 1
            #  Carry out a series of operations 
            if right-left+1 == window_size:
                min_value = min(min_value,window_value)
            right += 1

        return sum_ - min_value

This topic can actually be used as a template for sliding window topics

#  Let's go through the groups 
#  Carry out a series of operations （ Make a peace, etc ）
#  When the window length is exceeded 
#  Carry out a series of operations 
#  Move left border right 
#  When equal to the window length 
#  Combine the meaning of the question to find the answer 
#  Return results 

summary

The title of sliding window has been done for about fourorfive days , It's easier to solve the concerns after mastering them , I've been thinking , Don't let yourself go so “ fast ”, That is, swiping questions in a bolt , Slow yourself down , Be steady . Maybe the effect will be better .
This article has been written since 9 am , Until 4 p.m , It's also a review .
The resistance and long