Skip to content

08.Sliding window.md

Latest commit

 

History

History
143 lines (112 loc) · 10.5 KB

08.Sliding window.md

File metadata and controls

143 lines (112 loc) · 10.5 KB

8.Sliding window滑动窗口

  • substring(必须连续)
  • subarray(必须连续)
  • subsequence(可不连续)

1.滑动窗口 vs 双指针 vs 前缀和

2.滑动窗口模板

最先要考虑什么时候l要往前移动，就先写什么（终于把滑动窗口代码统一了，总是记不住）：

  • fix window: 不满足条件，l往前移动一步，所以先写不满足条件的分支
  • max window: 不满足条件，l往前移动直到满足条件（while）， 所以先写不满足条件的分支
  • min window: 满足条件，l往前移动知道不满足条件（while），所以写满足条件的分支

3.Fixed window problem

模板：r为right指针，r-k为left指针

for r, ch in enumerate(s):
    把 rth item 加到window
    
    #不满足条件, then move l to make window fix
    if r >= k:
        把 (r-k)th item 吐出来 to maintian a fixed size window
        
    #满足条件, update the result     
    if 满足条件：    
        更新 res
return

TODO: 683(H)

4.Find Max Window Size

l = 0
for r, ch in enumerate(s):
    把 rth item 加到window

    #不满足条件, then move l to make window satisfy condition
    while i < j and sums > target:
        sums = sums - nums[i]
        i += 1

    #满足条件, update the result    
    if sums <= target:
        cnt += j - i + 1  #以j结尾连续字串的个数

return cnt  #return result
  • 1208.Get_Equal_Substrings_Within_Budget.py (!!M)
    step 1: construct a cost arr; step 2: sliding window 第二种模板：find max subarray size for at most problem. 写法是while loop里让前面的指针去追后面的指针
  • 0904.Fruit_Into_Baskets.py (M)
  • 0487.Max_Consecutive_Ones_II (!!!M)
    sliding window solution: longest subarray with at most one 0s. 这题是at most problem, 写法是while loop里让前面的指针去追后面的指针. solution 2: record prev_lens and curr_lens for the previous lens of consecutive 1s and curr lens of consecutive 1s. update them we there is a new 0 coming, otherwise curr_lens += 1.
  • 1004.Max_Consecutive_Ones_III.py (!!!M)
    same as 487: longest subarray with at most k 0s. 这题是at most problem, 写法是while loop里让前面的指针去追后面的指针.
  • 0159.Longest_Substring_with_At_Most_Two_Distinct_Characters.py (!!M)
    Exactly the same as 340.
  • 0340.Longest_Substring_with_At_Most_K_Distinct_Characters.py (!!M)
    维护一个charDict, 用来记录i->j中的char的频率，这题是sum at most s problem, 写法是while loop里让前面的指针去追后面的指针; 更新j: charDict[s[j]+=1; 更新i: charDict[s[i]] -= 1, if charDict[s[i]] == 0: del charDict[s[i]]
  • 0424.Longest_Repeating_Character_Replacement.py (M)
    340 的变形题 this problem is to find the max_lens of substring so that (length of substring - number of times of the maximum occurring character in the substring) is at most K.
  • 0003.Longest_Substring_Without_Repeating_Characters.py (!!M)
    Soluition 0: sliding window, j - i + 1 > len(ch_to_cnt) check 是否有重复元素 Solution1: 简单做法，i [0,n] j[i,n] 判断有没有重复元素：set/hash/for loop scan it. Solution2: 类似209，维护一个included=set(), 用来记录i->j中include的char，套模板时满足的条件是s[j] not in included; 更新j: included.add(s[j]); 更新i: included.remove(s[i]).
  • 1100.Find_K-Length_Substrings_With_No_Repeated_Characters.py (!!M)
    Brutal force / sliding window with fixed length: O(26N); Sliding window O(N): find the substring longer than K that has no repeating chars.

TODO: 395

1248, 930, 992, 731 同类型题目，都是求数目

  • 1248.Count_Number_of_Nice_Subarrays (M)
    Solution:exactly(K) = atMost(K) - atMost(K-1); 第二种模板：find max subarray size for at most problem. 不满足条件更新i，满足条件更新结果res.
  • 0930.Binary_Subarrays_With_Sum (M)
    Solution:(number of subarrays having sum S) = (number of subarrays having sum at most S) - (number of subarrays having sum at most S-1) 这题是sum at most s problem, 写法是while loop里让前面的指针去追后面的指针. 904
  • 0992.Subarrays_with_K_Different_Integers.py (H)
    Solution:exactly(K) = atMost(K) - atMost(K-1). Helper function is exactly the same as 340. Longest Substring with At Most K Distinct Characters.
  • 0713.Subarray_Product_Less_Than_K.py (!!M)
    Note that the numbers are positive, so we can use sliding window. 这题是sum at most s problem

we can take 228 also as a sliding window

5.Find Min Window Size

总结:写法是while loop里让后面的指针j逐渐远离前面的指针i! i，j 移动j让满足条件>=target

l = 0
for r, ch in enumerate(s):
    把 rth item 加到window

    #满足条件, update the result, 移动i    
    while satisfy condition:
      update result
      l += 1
    
return result
  • 0209.Minimum_Size_Subarray_Sum (!!M)
    这题是第一种模板：find min subarray size for at least problem. 写法是while loop里让后面的指针逐渐远离前面的指针； Can we solve in O(NlogN)? Yes, we can traverse the the list, say at i, we search the fisrt j that satisfy sum(nums[i:]>=s), so it is a OOXX probelm, which could be solved using binary search. Follow up: 如果有负数怎么办？那就不能用sliding window了, 只能用pre_sum / deque, 详见862. Explanation: 维护一个sums, 用来记录i->j中数的和，套模板时满足的条件是sums < target; 更新j: sums += nums[j]; 更新i: sums -= nums[j] Can we solve in O(NlogN)? Yes, we can traverse the the list, say at i, we search the fisrt j that satisfy sum(nums[i:]>=s), so it is a OOXX probelm, which could be solved using binary search. Follow up: 如果有负数怎么办？那就不能用sliding window了，只能用deque. 详见239. 这题是sum at least s problem, 所以最好的写法是while loop里让后面的指针逐渐远离前面的指针； 如果是sum at most s problem, 写法是while loop里让前面的指针去追后面的指针.
  • 1234.Replace_the_Substring_for_Balanced_String (!!M)
    TODO：不懂 find the minimum substring so that outside the substring, condition all(four chars has frequency less than n//4) is satisfied. 第一种模板：find min subarray size for at least problem, 后面的指针去远离前面的指针。
  • 0727.Minimum_Window_Subsequence (H)
    solution 1: sliding window - O(MN) 这题subseq与上题substring不同，上题只需要freq都满足了就行，这题不仅如此，而且还是讲究顺序的，; solution 2: dp. dp[i][j] = the min window subsequence that ends with ith ch in t, and jth ch in s. If t[i-1] == s[j-1]: dp[i][j] = dp[i-1][j-1] + 1; else: dp[i][j] = dp[i][j-1] + 1
  • 0076.Minimum_Window_Substring (H)
    维护一个sourceFreqDict, 用来记录i->j中的char的频率，套用模板时满足的条件是sourceFreqDict all included in targetFreqDict; 更新j: sourceDict[s[j]] += 1, 更新i: sourceDict[s[i]] -= 1. time complexity is O(MN). solution 2: O(N), instead of using self.allIncluded(sourceDict, targetDict) to check matched or not, we use a int missing to keep track of how many chars are still needed in order to match, this reduce the time from O(M) to O(1). also, instead of using s[i:j] everytime when we renew res, we use start, end to renew the idx, which reduce time from O(N) to O(1) S[i:j] include i, not include j.

求数目1358