前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
社区首页 >专栏 >☆打卡算法☆LeetCode 209. 长度最小的子数组 算法解析

☆打卡算法☆LeetCode 209. 长度最小的子数组 算法解析

作者头像
恬静的小魔龙
发布于 2022-09-27 01:37:31
发布于 2022-09-27 01:37:31
23400
代码可运行
举报
文章被收录于专栏:Unity3DUnity3D
运行总次数:0
代码可运行

大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定一个整数数组和正整数target,找出数组中满足≥target的长度最小的子数组,返回其长度。”

题目链接:

来源:力扣(LeetCode)

链接: 209. 长度最小的子数组 - 力扣(LeetCode)

2、题目描述

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

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

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
示例 1:
输入: target = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的子数组。
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
示例 2:
输入: target = 4, nums = [1,4,4]
输出: 1

二、解题

1、思路分析

这道题要找出该数组中满足其和 ≥ target 的长度最小的连续子数组。

直观的方法是枚举数组中每个下标i作为子数组的开始下标,找到满足条件的下标j,然后更新子数组的最小长度也就是j-i+1,但是这种方法实现可能会超出时间限制。

上面说的方法时间复杂度为O(n2),因为找到长度最小的子数组需要O(n)的时间,要全部找一遍需要O(n2)的时间复杂度,那么能不能将时间优化一下呢。

常见的优化方法,可以使用二分查找,就可以将时间复杂度优化到O(log n),使用二分查找,需要创建一个数组用于存储数组的前缀和,前缀和就是从位置1到位置i这个区间内的所有的数字之和,对于每个开始下标i,通过二分查找得到大于或等于i的最小下标,更新子数组的最小长度。

2、代码实现

代码参考:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int ans = Integer.MAX_VALUE;
        int[] sums = new int[n + 1]; 
        // 为了方便计算,令 size = n + 1 
        // sums[0] = 0 意味着前 0 个元素的前缀和为 0
        // sums[1] = A[0] 前 1 个元素的前缀和为 A[0]
        // 以此类推
        for (int i = 1; i <= n; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }
        for (int i = 1; i <= n; i++) {
            int target = s + sums[i - 1];
            int bound = Arrays.binarySearch(sums, target);
            if (bound < 0) {
                bound = -bound - 1;
            }
            if (bound <= n) {
                ans = Math.min(ans, bound - (i - 1));
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

3、时间复杂度

时间复杂度:O(n log n)

其中n是数组的长度,需要遍历每个下标作为子数组的开始下标,通过二分查找得到长度最小的子数组,二分查找的时间复杂度是O(log n),总时间复杂度为O(n log n)。

空间复杂度:O(n)

其中n是数组的长度。

三、总结

因为这道题保证了数组中的每个元素都是正值。

那么前缀和一定是递增的,可以保证二分查找是不会出现问题的。

如果数组中不是每个元素都为正的话,就不能使用二分来查找位置了。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2022-08-23,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
LeetCode刷题DAY 33:长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的连续子数组,并返回其长度。如果不存在符合条件的连续子数组,返回 0。
三猫
2020/07/02
4990
每日一题:LeetCode-209. 长度最小的子数组(滑动窗口)
   🔎🔎如果说代码有灵魂,那么它的灵魂一定是👉👉算法👈👈,因此,想要写出💚优美的程序💚,核心算法是必不可少的,少年,你渴望力量吗😆😆,想掌握程序的灵魂吗❓❗️那么就必须踏上这样一条漫长的道路🏇🏇,我们要做的,就是斩妖除魔💥💥,打怪升级!💪💪当然切记不可😈走火入魔😈,每日打怪,拾取经验,终能成圣🙏🙏!开启我们今天的斩妖之旅吧!✈️✈️
用户11029129
2024/06/04
1110
每日一题:LeetCode-209. 长度最小的子数组(滑动窗口)
LeetCode 0209. 长度最小的子数组
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 numsl, numsl+1, ..., numsr-1, numsr ,并返回其长度。如果不存在符合条件的子数组,返回 0 。
Yano_nankai
2021/02/25
5760
LeetCode 0209. 长度最小的子数组
[优选算法]------滑动窗⼝——209. 长度最小的子数组
子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。
小李很执着
2024/06/15
980
[优选算法]------滑动窗⼝——209. 长度最小的子数组
图解LeetCode——209. 长度最小的子数组
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。
爪哇缪斯
2023/09/06
1950
图解LeetCode——209. 长度最小的子数组
209. 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, num
CaesarChang张旭
2021/06/21
1.6K0
209. 长度最小的子数组
[LeetCode] 209. Minimum Size Subarray Sum
该文是关于LeetCode的209. Minimum Size Subarray Sum,通过给定的正整数数组和目标正整数s,找出数组中和最小的连续子数组,使子数组的和大于等于s。有两种方法解决该问题,分别是思路一和方法二。思路一通过维护left和right两个指针以及sum变量,不断移动right指针来增加子数组和,同时通过sum-nums[left]不断缩小子数组和,直到找到符合条件的子数组。方法二通过开辟一个额外的数组sums来存储每个子数组的和,通过二分查找的方式在sums数组中找到最小的满足条件的子数组和。两种方法的时间复杂度分别为O(n)和O(nlogn)。
用户1148830
2018/01/03
7660
Leetcode模块训练3
1. 统计(优美子数组)(1048) 给你一个整数数组 nums 和一个整数 k。如果某个连续子数组中恰好有 k 个奇数数字, 我们就认为这个子数组是「优美子数组」。 请返回这个数组中 「优美子数组」 的数目。 示例 1: 输入:nums = [1,1,2,1,1], k = 3 输出:2 解释:包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。 示例 2: 输入:nums = [2,4,6], k = 1 输出:0 解释:数列中不包含任何奇数,所以不存在优美子数组。 示例
素履coder
2023/03/23
4440
LeetCode 第 45 场双周赛题解
对于一些给定了元素数据范围的题目,建议使用数据来进行统计,这样对于 Java 语言来说,代码会短些。
宫水三叶的刷题日记
2021/02/20
8350
LeetCode题解——数组篇
输入:n = 3 输出:[[1,2,3],[8,9,4],[7,6,5]] 示例 2: 输入:n = 1 输出:[[1]]
小点点
2022/12/12
3350
LeetCode题解——数组篇
红书2023秋招提前批算法真题解析
小红拿到了一个数组,她希望进行最多一次操作:将一个元素修改为x。小红想知道,最终的连续子数组最大和最大是多少?
五分钟学算法
2023/09/09
2860
红书2023秋招提前批算法真题解析
LeetCode. 209. 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组,并返回其长度。如果不存在符合条件的子数组,返回 0。
宇宙之一粟
2020/10/26
4730
209. 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的子数组。如果不存在符合条件的子数组,返回 0。
张伦聪zhangluncong
2022/10/26
1.1K0
LeetCode通关:数组十七连,真是不简单
数组基本上是我们最熟悉的数据结构了,刚会写“Hello World”不久,接着就是“杨辉三角”之类的练习。
三分恶
2021/08/10
3920
LeetCode LintCode和大于S的最小子数组Minimum Size Subarray Sum题目分析
给定一个由 n 个整数组成的数组和一个正整数 s ,请找出该数组中满足其和 ≥ s 的最小长度子数组。如果无解,则返回 -1。
desperate633
2018/08/22
9640
力扣209. 长度最小的子数组
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。
ccf19881030
2023/05/09
2460
【迎战蓝桥杯】 算法·每日一题(详解+多解)-- day7
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。
苏州程序大白
2022/05/09
2340
Leetcode | 第B节:数组综合题(2)
抱歉这一节相对隔得时间长了一些再发出来,因为这几天基本上主要时间都在关注东京奥运会的比赛现场。在发表这篇文章的时候,也恰好知道名将苏炳添以9‘83’‘的时间晋级决赛,我认为他可以以这个成绩再拿一次金牌,希望我的预言成真2333
学弱猹
2021/08/06
4160
图解LeetCode——209. 长度最小的子数组
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。
爪哇缪斯
2023/06/16
3300
图解LeetCode——209. 长度最小的子数组
刷题日记-Day2- Leedcode-977. 有序数组的平方,209. 长度最小的子数组,59. 螺旋矩阵 II-Python实现
链接:https://leetcode.cn/problems/squares-of-a-sorted-array/description/
种花家的奋斗兔
2024/05/25
641
刷题日记-Day2- Leedcode-977. 有序数组的平方,209. 长度最小的子数组,59. 螺旋矩阵 II-Python实现
推荐阅读
相关推荐
LeetCode刷题DAY 33:长度最小的子数组
更多 >
领券
社区富文本编辑器全新改版!诚邀体验~
全新交互,全新视觉,新增快捷键、悬浮工具栏、高亮块等功能并同时优化现有功能,全面提升创作效率和体验
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
查看详情【社区公告】 技术创作特训营有奖征文