[leetcode 209]长度最小的子数组（Python+二分查找+双指针）

╰+攻爆jí腚メ 2023-02-21 01:53 6阅读 0赞

## 题目描述 ##

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

示例:

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

进阶:

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

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

--------------------

## 结题思路 ##

#### 思路一：暴力遍历：（Python超时） ####

初始化子数组的最小长度为无穷大，枚举数组 nums 中的每个下标作为子数组的开始下标，对于每个开始下标 i，需要找到大于或等于 i 的最小下标 j，使得从 **nums\[i\]** 到 **nums\[j\]** 的元素和大于或等于 s，并更新子数组的最小长度（此时子数组的长度是 **j-i+1**）。

**- 复杂度分析**

1.  时间复杂度： O ( n 2 ) O(n^2) O(n2)， n n n为数组长度。
2.  空间复杂度： O ( 1 ) O(1) O(1)

#### 思路二：二分查找+前缀和 ####

暴力法中再确定每个子数组的开始下标后，找到长度最小的子数组需要 O ( n ) O(n) O(n)的时间。如果使用二分查找，可以将时间复杂度降到 O ( l o g n ) O(logn) O(logn)。  
使用二分查找要额外创建一个数组用来存储数组 n u m s nums nums的前缀和，其中 s u m s \[ i \] sums\[i\] sums\[i\]表示从 n u m s \[ 0 \] nums\[0\] nums\[0\]到 n u m s \[ i − 1 \] nums\[i-1\] nums\[i−1\]的元素和。得到前缀和之后对于每个开始下标i，可以通过二分查找得到>=i的最小下标 b o u n d bound bound，使得 s u m s \[ b o u n d \] − s u m s \[ i − 1 \] ≥ s sums\[bound\]-sums\[i-1\] ≥ s sums\[bound\]−sums\[i−1\]≥s，并更新子数组的最小长度。  
因为题目中的数组元素均为正数，所以前缀和一定是递增的，这是使用二分查找的正确性的前提。`Python`中`bisect.bisect_left`实现了二分查找大于等于某个数的第一个位置的功能。

**- 复杂度分析**

1.  时间复杂度： O ( n l o g n ) O(nlogn) O(nlogn)， n n n为数组长度。
2.  空间复杂度： O ( n ) O(n) O(n)，额外创建数组sums存储前缀和。

#### 思路三：双指针 ####

前两种方法都是每次确定子数组的开始下标后得到长度最小的子数组，为了降低时间复杂度可以使用双指针。  
定义指针  s t a r t start start 和  e n d end end 分别表示子数组的开始位置和阶数位置，维护变量  s u m sum sum 存储子数组中的元素和。  
开始时  s t a r t start start 和  e n d end end 都指向下标0， s u m = 0 sum=0 sum=0。  
每一轮迭代都将  n u m s \[ e n d \] nums\[end\] nums\[end\] 加到  s u m sum sum 中，如果  s u m ≥ s sum≥s sum≥s ，更新子数组的最小常数，然后从  s u m sum sum 中减掉  n u m s \[ s t a r t \] nums\[start\] nums\[start\] ，并把  s t a r t start start 右移，直到  s u m < s sum<s sum<s ，此过程中要更新子数组最小长度。每轮迭代后将  e n d end end 后移。

**- 复杂度分析**

1.  时间复杂度： O ( n ) O(n) O(n)，其中 n n n是数组的长度。指针  s t a r t start start 和  e n d end end 最多各移动  n n n 次。
2.  空间复杂度： O ( 1 ) O(1) O(1)。

--------------------

## 代码实现 ##

#### 思路二：二分查找+前缀和 ####

class Solution:
        def minSubArrayLen(self, s, nums):
            if not nums:
                return 0
            
            n = len(nums)
            ans = n + 1
            sums = [0]
            for i in range(n):
                sums.append(sums[-1] + nums[i])
            
            for i in range(1, n + 1):
                target = s + sums[i - 1]
                bound = bisect.bisect_left(sums, target)
                if bound != len(sums):
                    ans = min(ans, bound - (i - 1))
            
            return 0 if ans == n + 1 else ans
    
    #作者：LeetCode-Solution
    #链接：https://leetcode-cn.com/problems/minimum-size-subarray-sum/solution/chang-du-zui-xiao-de-zi-shu-zu-by-leetcode-solutio/

### 思路三：双指针 ###

class Solution(object):
        def minSubArrayLen(self, s, nums):
            n = len(nums)
            start, end = 0,0
            mysum = 0
            ans = n+1
            while end < n:
                mysum += nums[end]
                while mysum >= s:
                    ans = min(ans, end-start+1)
                    mysum -= nums[start]
                    start += 1
                end += 1
    
            return 0 if ans == n+1 else ans

--------------------

## Tips ##

1.  涉及连续子数组的问题通常有两种思路：一是`滑动窗口`、二是`前缀和`。
2.  `Python`中`bisect.bisect_left`实现了二分查找大于等于某个数的第一个位置的功能。

--------------------

A u t h o r : C h i e r Author: Chier Author:Chier