每日一题：LeetCode-209. 长度最小的子数组

作者：半亩房顶

2024-01-17
北京
本文字数：1534 字
阅读完需：约 5 分钟

刷题使我快乐，满脸开心.jpg

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-size-subarray-sum/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

给定一个含有 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

复制代码

提示：

1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105

进阶：

如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

思路

暴力可破，关键就在于怎么优化了。

前缀和 + 滑动窗口

最开始想到的是滑动窗口，大体思路就是
定义两个边界，先增加右边界扩张窗口，看是否存在满足条件的子数组
维持住窗口往右滑动，依然满足条件的情况下，增加左边界收缩窗口看能否缩小窗口
正好最近做过一道前缀和的题目，感觉有了前缀和就能够省去在操作窗口的同时增减元素判断是否满足了，所以加入了前缀和的思路

基本思路就是如此了，具体见代码注释

前缀和 + 二分搜索

这个进阶有点费解哈，不过能扩展一个思路也是没问题的二分搜索的思路大体如下：

先求出前缀和方便搜索
固定左边界，从左到右依次尝试
固定左边界的情况下，尝试找出满足 >=target 条件的最左元素，即右边界
左右边界之间就是满足条件的子数组了，尝试更新最小长度

这里二分搜索的代码是官方题解的代码，感兴趣可以自己实现一下二分查找。

代码

前缀和 + 滑动窗口

func minSubArrayLen(target int, nums []int) int {    // 求个前缀和，可以不用前缀和，在后面循环中直接加和求解也可    sums := make([]int, len(nums)+1)    for i := 0; i < len(nums); i++ {        sums[i+1] = sums[i] + nums[i]    }
    fast, slow := 1, 0    res := 0    for fast < len(sums) {        // < target，继续递增fast        // >= target，跟上slow        if sums[fast]-sums[slow] >= target {            // 跳过不需要的答案步骤，直接看是否能够优化结果            // 思路上就是滑动窗口的思路，有了更小的窗口，就不考虑更大的了            if res > 0 {                slow = fast - res            }            for sums[fast]-sums[slow] >= target {                res = fast - slow                slow++            }        }        fast++    }    return res}

复制代码

前缀和 + 二分法

func minSubArrayLen(s int, nums []int) int {    n := len(nums)    if n == 0 {        return 0    }    ans := math.MaxInt32    sums := make([]int, n + 1)    // 为了方便计算，令 size = n + 1     // sums[0] = 0 意味着前 0 个元素的前缀和为 0    // sums[1] = A[0] 前 1 个元素的前缀和为 A[0]    // 以此类推    for i := 1; i <= n; i++ {        sums[i] = sums[i - 1] + nums[i - 1]    }    for i := 1; i <= n; i++ {        target := s + sums[i-1]        bound := sort.SearchInts(sums, target)        // 这一段不用太纠结        // 本质就是用二分法去找 >=target 的边界值        if bound < 0 {            bound = -bound - 1        }        if bound <= n {            ans = min(ans, bound - (i - 1))        }    }    if ans == math.MaxInt32 {        return 0    }    return ans}

复制代码

欢迎关注公众号交流更多题目~

发布于: 刚刚阅读数: 5

原文链接:【http://xie.infoq.cn/article/707d6c3dd4578e9f6e0ac10e9】。文章转载请联系作者。

半亩房顶

关注

人生那么长，能写多少bug？ 2018-11-16 加入

我希望，自己永远是自己。我希望，远离bug。

发布

暂无评论

创作场景

每日一题：LeetCode-209. 长度最小的子数组

题目

思路

前缀和 + 滑动窗口

前缀和 + 二分搜索

代码

前缀和 + 滑动窗口

前缀和 + 二分法

半亩房顶

评论