LeetCode 209. 长度最小的子数组 | Python

标签：初始化   指针   ret   ima   mini   water   sub   img   输出   

209. 长度最小的子数组

题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/minimum-size-subarray-sum

题目

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的连续子数组，返回 0。

示例:

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

进阶:

如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。

解题思路

思路：双指针 / 前缀和+二分查找

先看题目，题目说明，数组 nums 给定的元素都是正整数，同时给一个整数 s，求子数组和大于等于 s 的最小连续子数组，返回长度。不存在则返回 0。

这里先说下特殊情况，上面根据题意已说明，nums 中的元素都是正整数，那么如果数组所有元素和都小于 s 的话，那么子数组是一定不能满足要求的，直接返回 0 即可。

进阶 提示的内容部分中，要求先完成 O(n) 时间复杂度的解法。这就是我们现在要说明的 双指针 思路的解法。

具体的实现思路：

• 先定义双指针 left，right，同时指向索引为 0 的初始位置；
• 定义 num_sum 存储数组和，用以与 s 比较；
• 先移动右指针，维护更新 num_sum 值，当 num_sum 满足大于等于 s 的条件时，先记录此时的数组长度，然后尝试缩小数组的长度。
• 此时移动左指针，剔除左边的元素，再次判断 num_sum 和 s 的值。循环直至指针到达末尾位置。

双指针实现思路的过程，可见下图：

关于图中的参数
当 num_sum 大于等于 s 时表示满足条件。
s：题目所给的目标值
num_sum：子数组之和
left：左指针
right：右指针
ans：满足条件的子数组长度

具体的代码见 【代码实现 # 双指针】。

上面是双指针的思路，下面尝试使用 O(nlogn) 复杂度的方法：前缀和 + 二分查找。

关于前缀和，这里就不展开说明这个概念了。这里我们用数组 num_sum 存储 nums 的前缀和。

num_sum[i]：表示 nums[0] 到 nums[i-1] 的元素之和。

还是因为有 【给定一个含有 n 个正整数的数组】 的前提，那么我们存储前缀和的数组一定是递增升序的，这样也能保证二分查找的正确性。

当我们得到存储前缀和的数组之后，我们可以遍历数组通过二分查找得到一个索引 index，使得 num_sum[index] - num_sum[i-1] >= s，更新维护子数组的长度，（此时的长度为 index -(i-1)）

具体的代码见 【代码实现 # 前缀和+二分查找】。

代码实现

# 双指针
class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        # 先处理特殊情况，因为给定的数组都是正整数
        # 如果数组中所有元素的和都小于 s
        # 那么子数组的和一定都小于 s，直接返回 0
        if sum(nums) = s:
                ans = min(ans, right - left + 1)
                num_sum -= nums[left]
                left += 1
            right += 1
        
        return ans


# 前缀和+二分查找
class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        def bin_search(num_sum, left, right, target):
            while left = target else -1
        
        # 先处理特殊情况，当数组中的元素和小于 s，
        # 则表示数组中所有子数组的和都不可能大于 s
        # 这个时候，直接返回 0
        if sum(nums) 

实现结果

双指针 | 实现结果

前缀和+二分查找 | 实现结果

总结

• 题目中说明，给定的数组元素都是正整数，这是个一个大前提，能够有效的帮助解决问题。
• 题目中要求先实现 O(n) 时间复杂度的解法。这里使用双指针的方法，具体实现如下：
  • 初始化双指针 left, right，定义变量 num_sum 存储子数组的和。
  • 当 num_sum 小于目标值 s 时，先移动右指针，维护更新 num_sum。当 num_sum 满足条件也就是大于或等于 s 时，先记录此时子数组的长度。此时移动左指针尝试缩小数组，再次比较 num_sum 和 s 的值。循环判断直至 right 到达末尾位置。
• 题目进阶说可以尝试 O(nlogn) 时间复杂度的解法，这里可联想到二分查找。同样根据第一项所说的前提，可以定义数组存储 nums 数组的元素前缀和。具体实现如下：
  • 定义 num_sum 存储数组的前缀和，num_sum[i] 表示 nums[0] 到 nums[i-1] 元素之和。
  • 通过二分查找，可以定位到一个索引 index 使得 num_sum[index]-nums[i-1] 的和大于或等于 s，记录此时的子数组长度（index-(i-1)）。

文章原创，如果觉得写得好，欢迎关注点赞。微信公众号《书所集录》同步更新，同样欢迎关注点赞。

LeetCode 209. 长度最小的子数组 | Python

标签：初始化   指针   ret   ima   mini   water   sub   img   输出   

原文地址：https://www.cnblogs.com/yiluolion/p/13205009.html