Leetcode-滑动窗口

题目要求

连续子数组

解题思路

  • 根据要求，找到第一个满足条件的窗口
  • 调整窗口(右移/左移)使其继续满足要求，并进行重复
  • 得到最合适的窗口即为答案

Leetcode例题

无重复字符的最长子串
1
2
3
4
5
6
7
8
9
10
11
12
def lengthOfLongestSubstring(s):
    if len(s) == 0: return 0
    window_start,res = 0,0
    dic = {}
    for window_end in range(len(s)):
        char = s[window_end]
        if char in dic and dic[char]>=window_start: # 注意这里的第二个条件dic[char]>=window_start！！ 起到一个覆盖的作用
            window_start = dic[char] +1
        dic[char] = window_end
        width = window_end-window_start+1
        res = max(width,res)
    return res
大小为 K 且平均值大于等于阈值的子数组数目
1
2
3
4
5
6
7
8
9
10
11
12
def numOfSubarrays(arr,k,threshold):
    if arr == [] or len(arr)<k:return 0
    window_sum,window_start,res = 0,0,0
    temp = threshold*k
    for window_end in range(len(arr)):
        window_sum+=arr[window_end]
        if window_end>=k-1:
            if window_sum >=temp:
                res+=1
            window_sum-=arr[window_start]
            window_start+=1
    return res
替换后的最长重复字符
1

最小覆盖子串
滑动窗口中位数
滑动窗口最大值
Algorithm
Leetcode Python

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！