学习笔记--算法(滑动窗口)9

embedded/2024/11/14 3:02:17/

长度最小的子数组

链接:

. - 力扣(LeetCode)

题目:给定一个含有 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 <= 10^9

1 <= nums.length <= 10^5

1 <= nums[i] <= 10^5


解法一

图解

算法思路

「从前往后」枚举数组中的任意⼀个元素,把它当成起始位置。然后从这个「起始位置」开始,然

后寻找⼀段最短的区间,使得这段区间的和「⼤于等于」⽬标值。

将所有元素作为起始位置所得的结果中,找到「最⼩值」即可。

代码省略,超时。


解法二(滑动窗口)

算法思路

由于此问题分析的对象是「⼀段连续的区间」,因此可以考虑「滑动窗⼝」的思想来解决这道题。让滑动窗⼝满⾜:从 i 位置开始,窗⼝内所有元素的和⼩于 target (那么当窗⼝内元素之和第⼀次⼤于等于⽬标值的时候,就是 i 位置开始,满⾜条件的最⼩⻓度)。

做法:将右端元素划⼊窗⼝中,统计出此时窗⼝内元素的和:

▪ 如果窗⼝内元素之和⼤于等于 target :更新结果,并且将左端元素划出去的同时继续判断是否满⾜条件并更新结果(因为左端元素可能很⼩,划出去之后依旧满⾜条件)

▪ 如果窗⼝内元素之和不满⾜条件: right++ ,另下⼀个元素进⼊窗⼝。

为何滑动窗⼝可以解决问题,并且时间复杂度更低?

▪ 这个窗⼝寻找的是:以当前窗⼝最左侧元素(记为 left1 )为基准,符合条件的情况。也就是在这道题中,从 left1 开始,满⾜区间和 sum >= target 时的最右侧(记为right1 )能到哪⾥。

▪ 我们既然已经找到从 left1 开始的最优的区间,那么就可以⼤胆舍去 left1 。但是如果继续像⽅法⼀ 样,重新开始统计第⼆个元素( left2 )往后的和,势必会有⼤量重复的计算(因为我们在求第⼀段区间的时候,已经算出很多元素的和了,这些和是可以在计算下次区间和的时候⽤上的)。

▪ 此时, rigth1 的作⽤就体现出来了,我们只需将 left1 这个值从 sum 中剔除。从right1 这个元素开始,往后找满⾜ left2 元素的区间(此时 right1 也有可能是满⾜的,因为 left1 可能很⼩。 sum 剔除掉 left1 之后,依旧满⾜⼤于等于target )。这样我们就能省掉⼤量重复的计算。

▪ 这样我们不仅能解决问题,⽽且效率也会⼤ 提升。

时间复杂度:虽然代码是两层循环,但是我们的 left 指针和 right 指针都是不回退的,两者最多都往后移动 n 次。因此时间复杂度是 O(N) 。

图解

举例


代码

public int minSubArrayLen(int target, int[] nums) {int n = nums.length;int sum = 0;int len = Integer.MAX_VALUE;//由于在最开始的时候,如果len定义为0,就会导致在下面进行第一次出窗口比较len的时候,由于0比任何数都小,会导致输出结果为0,错误解答//left = 0,right = 0for(int left = 0,right = 0;right < n;right++){//进窗口sum += nums[right];//判断,如果sum>= target,就进行统计更新len,然后出窗口,再判断是否结束(right是否越界),未结束就让left++while(sum >= target){len = Math.min(len,right - left + 1);sum -= nums[left];left++; }}//如果没有找到满足target的子数组,就需要返回0return len == Integer.MAX_VALUE ? 0 : len; 
}


http://www.ppmy.cn/embedded/96628.html

相关文章

C#中的S7协议

S7协议-S7COMM S7COMM 进行写 CTOP->PDU type已知枚举值 0X0E连接请求0x0d连接确认0x08断开请求0x0c断开确认0x05拒绝访问0x01加急数据0x02加急数据确认0x04用户数据0x07TPDU错误0x0f数据传输 S7Header->ROSCTR已知枚举值 0X01JOB REQUEST。主站发送请求0x02Ack。从站…

Java集合框架高级特性、并发编程深入与高级特性概览

第七天&#xff1a;Java集合框架高级特性、并发编程深入与高级特性概览 1. Java集合框架高级特性 并发集合&#xff1a;深入了解Java并发包&#xff08;java.util.concurrent&#xff09;中提供的并发集合&#xff0c;如ConcurrentHashMap、CopyOnWriteArrayList等。理解它们…

Linux 与 Windows 服务器操作系统 | 全面对比

在服务器操作系统的领域&#xff0c;Linux 和 Windows 一直是两个备受关注的选择。 首先来看 Windows 操作系统。它由 Microsoft Corporation 开发&#xff0c;在桌面领域占据显著份额&#xff0c;其中 Windows 10 是使用最广泛的版本&#xff0c;广泛应用于个人计算机和企业桌…

出版广角期刊

投稿指南 相关描述&#xff1a;出版广角杂志官方网站,出版广角杂志,出版广角杂志社,出版广角属于类型期刊&#xff0c;由广西期刊传媒集团有限公司主办&#xff0c;国内统一刊号&#xff1a;45-1216/G2&#xff0c;国际标准刊号&#xff1a;1006-7000&#xff0c;&#xff0c;…

如何使用和配置 AWS CLI 环境变量?

欢迎来到雲闪世界。环境变量在配置和保护应用程序方面起着至关重要的作用&#xff0c;在使用 AWS CLI&#xff08;命令行界面&#xff09;时&#xff0c;它们的使用尤其重要。在这篇博客文章中&#xff0c;我们将深入探讨环境变量的世界&#xff0c;探索它们的用途、它们在 AWS…

跟《经济学人》学英文:2024年08月10日这期 A history-lover’s guide to the market panic over AI

A history-lover’s guide to the market panic over AI Past technologies offer clues to what comes next 原文&#xff1a; Andrew Odlyzko, a professor of mathematics at the University of Minnesota, has a side hustle: he has become one of the world’s foremo…

Therabody™明星产品TheragunⓇ筋膜枪,以科技健康助力舞台高光时刻

&#xff08;2024 年 8月16日&#xff0c;中国上海&#xff09;近日&#xff0c;热门音乐竞演综艺《披荆斩棘》携最新一季热血回归&#xff0c;节目邀请三十四位知名男艺人走上舞台&#xff0c;带来精彩绝伦的表演&#xff0c;受到广大观众的喜欢。Therabody™的明星产品Therag…

坐牢第二十七天(聊天室)

基于UDP的网络聊天室 一.项目需求&#xff1a; 1.如果有用户登录&#xff0c;其他用户可以收到这个人的登录信息 2.如果有人发送信息&#xff0c;其他用户可以收到这个人的群聊信息 3.如果有人下线&#xff0c;其他用户可以收到这个人的下线信息 4.服务器可以发送系统信息…