MyNote
0%

双指针——滑动窗口 Two Pointer--Sliding Window

Posted on Edited on In

双指针——滑动窗口

滑动窗口代码模板

在数组arr中，arr[i…j]为滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
i,j = 0,-1  #初始时，窗口中不能有元素，右边界为-1
"""
result 初始值
辅助变量等
"""

while i<len(arr): #只要窗口左边不越界，就能一直滑动下去
    
    if j+1<len(arr) and condition: #只要窗口右边界不越界，且满足题目条件时进行操作
        j+=1 
        process(arr[j])
    
    else:  #当前窗口不满足题目条件时，先进行操作，再使左边界向前滑动
        process(arr[i]) 
        i-=1
"""
    记录，并更新result
"""

return result

LeetCode 209 Minimum Size Subarray Sum

https://leetcode.com/problems/minimum-size-subarray-sum/

题目理解：给定我们一个数字，让我们求子数组之和大于等于给定值的最小长度

Input: s = 7, nums = [2,3,1,2,4,3]

Output: 2

解释：满足子数组和=7的最小长度数组是[4,3],所以output=2

解法1：暴力解法：

遍历所有的连续子数组[i..j]，计算其和sum，验证sum>=s，时间复杂度为O(n^3)

最大问题：大量重复计算

解法2：滑动窗口

整个过程保持一个窗口，而这个窗口的长度不是固定的，且不停向前滑动

从i到j的一个连续子数组构成滑动窗口

图1

如果当前这个子数组nums[i...j]中元素的和sum<s的话，则j向前移动一位，并将nums[j+1]纳入子数组中。j+1不能越界。

图2

j继续向前移动直到子数组的和sum>s，并记录当前的i和j之间的距离（子数组长度）

图3

随后从i端缩小这个连续子数组。

注意：代码实现时，要先是移除i所指元素，再进行i++

图4

直到sum<s，此时j又可以继续前进，去寻找下一个符合条件的连续子数组。左边界不越界就能一直滑下去。

图5

代码实现

注意：这个窗口是前闭后闭的区间，初始时不能有任何元素，因此j需要从-1开始

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        i,j = 0,-1 #注意j从-1开始
        sum = 0  #初始时sum为0
        res = len(s)+1 #初始设置为不可能取到的一个最大值
       
      #窗口滑动的过程，只要左边界不越界就能滑动下去
        while i<len(nums):
            if sum<s and j+1<len(s):#j+1不能越界 
                j+=1  #j向前滑动，并将所指元素纳入子数组中
                sum+=nums[j]
            else: #sum>=s，先移除i所指元素，i向前移动
                sum-=nums[i]
                i+=1
            
            #经过一系列操作后，满足条件的子数组出现了
            #此时存储当前满足条件的子数组的结果
            if sum >= s: 
                res = min(res,j-l+1)
        #注意：遍历一遍没有解的情况
        if res == len(nums): 
            return 0
        return res

其他例题

子数组类题目

序号 题目 难度 代码
78 Subsets medium python、java、c++
90 Subsets II medium python、java、c++
53 Maximum Subarray easy python、java、c++
152 Maximum Product Subarray medium python、java、c++
239 Sliding Window Maximum hard python、java、c++
295 Find Median from Data Stream hard python、java、c++
228 Summary Ranges medium python、java、c++
163 Missing Ranges medium python、java、c++
325 Maximum Size Subarray Sum Equals k medium python、java、c++
209 Minimum Size Subarray Sum medium python、java、c++
238 Product of Array Except Self medium python、java、c++
128 Longest Consecutive Sequence Hard python、java、c++