AI毛毛的blog

leetcode打卡-0209长度最小的子数组

题目描述

给定一个含有n个正整数的数组和一个正整数target 。

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

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/minimum-size-subarray-sum

示例：

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

解题思路

1. 前缀和 + 二分查找

数组中查找相关的题目，可以考虑二分查找提高效率，但是二分查找适用于有序数组。题目中这个数组是正数序列，于是就想到先把这个数组的前缀和计算出来，保证形成的是一个从小到大的有序序列。

长度为n的数组nums，生成一个长度为n+1首位为0的前缀和数组sums，则sums[j]-sums[i]，即为nums的i到j-1位之和。

得到前缀和之后，对于每个开始下标i，可通过二分查找得到大于或等于i的最小下标bound，使得sums[bound]-sums[i-1]>target，并更新子数组的最小长度，此时子数组的长度是bound−(i−1)。

本来手写了个二分查找，看了题解后才知道原来Python标准库里有个bisect的模块已经实现了二分查找，就直接用它好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        if not nums:
            return 0
     
        n = len(nums)
        ans = n + 1
        sums = [0] * (n + 1)
        for i, val in enumerate(nums):
            sums[i + 1] = sums[i] + val
        for i in range(1, n + 1):
            tmp = target + sums[i - 1]
            bound = bisect.bisect_left(sums, tmp)
            if bound != len(sums):
                ans = min(ans, bound - (i - 1))
        return 0 if ans == n + 1 else ans
  • 时间复杂度: O(nlogn)
  • 空间复杂度: O(n)

209_01.png

2. 滑动窗口

看了官方题解才发现这题能够转换为滑动窗口问题，真是没想到。

滑动窗口的精髓在于放大窗口与缩小窗口的过程中，不断调整范围以适应目标，最终找到最优解。这道题求范围之和，正好可以用滑动窗口的思路来调节范围。

用两个指针start和end指向窗口的起始与终止位置，维护一个变量sums不断存储窗口中的元素之和。

  1. end不断后移，扩大窗口范围，sum += nums[end]，直到sums >= target
  2. 更新窗口的最小长度
  3. start后移，缩小窗口范围，sums -= nums[start]，直到sums < target
  4. 更新窗口的最小长度，继续循环
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, target: int, nums: List[int]) -> int:
        if not nums:
            return 0
        
        if nums[0] >= target:
            return 1

        n = len(nums)
        ans = n + 1
        start = 0
        total = 0

        # 外层通过右移end增大窗口
        for end in range(n):
            total += nums[end]
            while total >= target:
                ans = min(ans, end - start + 1)

                # 内层通过右移start缩小窗口
                total -= nums[start]
                start += 1

        return 0 if ans == n + 1 else ans
  • 时间复杂度O(n)
  • 空间复杂度O(1)

209_02.png

Rust刚学，不太熟练，直接从Python代码翻译着写了，以后熟练了看看能不能优化一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
impl Solution {
    pub fn min_sub_array_len(target: i32, nums: Vec<i32>) -> i32 {
        if (nums.is_empty()) {
            return 0;
        }

        if (nums[0] >= target) {
            return 1;
        }

        let n = nums.len();
        let mut ans = n + 1;
        let mut start = 0;
        let mut total = 0;

        for end in 0..n {
            total += nums[end];
            while total >= target {
                ans = ans.min(end - start + 1);
                total -= nums[start];
                start += 1;
            }
        }

        if ans == n + 1 {
            0
        } else {
            ans as i32
        }
    }
}

总结

区间问题转换为滑动窗口问题，有些场合下是个比较好的思路，可以多练习练习。