刷题第2天（中等题）：LeetCode209--长度最小的子数组--双指针思路（滑动窗口法）

LeetCode209-长度最小的子数组：给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

思路分析：这道题最暴力的解法是两个for循环，一个控制数组的起始位置，一个控制数组的终止位置，不断地寻找符合条件的子序列，但这种方法的时间复杂度是O(n2）。这种解法目前已经超时，无法通过。

这道题我们可以使用数组操作中另一个常用的滑动窗口方法：不断的调节子序列的起始位置和终止位置，从而得出我们想要的结果。

实现滑动窗口，主要需要确定三点：1.窗口内是什么？；2.如何移动窗口的起始位置？；3.如何移动窗口的结束位置？

窗口就是满足其和》=target的长度最小的连续子数组；

窗口起始位置移动：如果当前窗口的值大于target了，窗口就要向前移动了；

窗口终止位置移动：窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。

具体为使用一个指针进行循环来遍历滑动窗口的终止位置，使用一个指针变量来逐步更新起始位置。

具体代码：

# 滑动窗口法
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        L = len(nums)
        left = 0
        right = 0
        min_len = float("inf")
        cur_sum = 0 # 当前的累加值

        while right < L:  # 不要等于，索引从0开始，等于会下标越界
            cur_sum += nums[right]

            while cur_sum >= target: 当前累加值大于目标值
                min_len = min(min_len, right - left + 1)
                cur_sum -= nums[left]  
                left += 1
            right += 1
        
        return min_len if min_len != float("inf") else 0

总结：注意题干中的连续子数组很关键，这才是使用滑动窗口的重要前提，如果不是连续的就不能用滑动窗口法。代码中第一个while循环中right用来控制滑动窗口的终止位置。第二个内层while用来判别是否窗口内的值大于target，当窗口内的值的和足够大的时候，记录并比较历史记录中最小的窗口的长度。然后将窗口最左边的值减掉，终止指针right加1，实现窗口的滑动。

原文地址：https://blog.csdn.net/qq_43449643/article/details/136356201

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！