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的模块已经实现了二分查找,就直接用它好了。

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. 更新窗口的最小长度,继续循环
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代码翻译着写了,以后熟练了看看能不能优化一下。

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
        }
    }
}

总结

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