【滑动窗口】| 力扣高频题: 长度最小的数组

2024-09-06 14:28

本文主要是介绍【滑动窗口】| 力扣高频题: 长度最小的数组,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

🎗️ 主页:小夜时雨
🎗️专栏:算法题
🎗️如何活着,是我找寻的方向

优雅

目录

  • 1. 题目解析
  • 2. 代码

1. 题目解析

题目链接: https://leetcode.cn/problems/minimum-size-subarray-sum/description/ (可点击)

在这里插入图片描述

本道题是滑动窗口的一道经典应用问题:找出数组中长度最小的子数组。

滑动窗口优化思路:

利用滑动窗口来优化暴力枚举思路。

暴力枚举:两层 for 循环,固定一个起点,遍历出所有的子数组,然后找到满足条件的子数组,并在找到子数组的过程中,更新长度即可。
时间复杂度:两层 for 循环, 所以是 O(n ^ 2)

优化思路:

两个指针:left 和 right,每次固定 left,right 向后遍历数组。

  1. 优化1: 数组元素是大于 0 的,每次向后累加,和肯定都是变大的。所以当满足条件之后,在往后累加, 和肯定也是满足条件的,但是长度肯定就会变长,就不是最短的,所以不用遍历到最后。
  2. 优化2:找到和满足条件后,更新结果记录长度,此时 left 向后移动,但是 right 不用回退到 left 处进行遍历。因为这个和我们也是可以知道的, 就是 ret - nums[left] 的。 所以就可以直接进行判断。

优化之后的时间复杂度: 虽然是两层循环,但是是 O(n + n) = O(2n) = O(n).

接下来的代码里还会再次进行强调的,看下面的图更容易理解:

在这里插入图片描述

2. 代码

看下面的代码对照着上面的优化流程解析可能会更加的清楚。

public int minSubArrayLen(int target, int[] nums) {// 滑动窗口三步: 1. 初始值//               2. 进窗口//               3. 判断 出窗口//                    更新结果,这个视具体而定// 时间复杂度是 O(N),空间复杂度 O(1)int sum = 0; // 标记总和int len = Integer.MAX_VALUE; // 标记长度 , 求的最小值,防止干扰结果for(int left = 0,right = 0; right < nums.length; right++ ) {sum += nums[right]; // 1. 进窗口// 2. 判断, 注意 left 不要越界. 加不加都行, 因为越界的话 sum = 0了 不会大于target. 这个判断也过不去, 但是最好加上, 有的就需要加上. 保持习惯// while(left < n && sum >= target) {while(sum >= target) { // 2.判断结果                        len = Math.min(len, right - left + 1); // 更新结果sum -= nums[left]; // 3.出窗口left++; }                          }// 可能没结果return len == Integer.MAX_VALUE ? 0 : len;}

🎗️🎗️🎗️ 好啦,到这里有关本题的分享就没了,如果感觉做的还不错的话可以点个赞,关注一下,你的支持就是我继续下去的动力,我们下期再见,拜了个拜~ ☆*: .。. o(≧▽≦)o .。.:*☆

这篇关于【滑动窗口】| 力扣高频题: 长度最小的数组的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1142263

相关文章

Windows的CMD窗口如何查看并杀死nginx进程

《Windows的CMD窗口如何查看并杀死nginx进程》:本文主要介绍Windows的CMD窗口如何查看并杀死nginx进程问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录Windows的CMD窗口查看并杀死nginx进程开启nginx查看nginx进程停止nginx服务

MySQL JSON 查询中的对象与数组技巧及查询示例

《MySQLJSON查询中的对象与数组技巧及查询示例》MySQL中JSON对象和JSON数组查询的详细介绍及带有WHERE条件的查询示例,本文给大家介绍的非常详细,mysqljson查询示例相关知... 目录jsON 对象查询1. JSON_CONTAINS2. JSON_EXTRACT3. JSON_TA

JAVA数组中五种常见排序方法整理汇总

《JAVA数组中五种常见排序方法整理汇总》本文给大家分享五种常用的Java数组排序方法整理,每种方法结合示例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录前言:法一:Arrays.sort()法二:冒泡排序法三:选择排序法四:反转排序法五:直接插入排序前言:几种常用的Java数组排序

使用WPF实现窗口抖动动画效果

《使用WPF实现窗口抖动动画效果》在用户界面设计中,适当的动画反馈可以提升用户体验,尤其是在错误提示、操作失败等场景下,窗口抖动作为一种常见且直观的视觉反馈方式,常用于提醒用户注意当前状态,本文将详细... 目录前言实现思路概述核心代码实现1、 获取目标窗口2、初始化基础位置值3、创建抖动动画4、动画完成后

Java实现按字节长度截取字符串

《Java实现按字节长度截取字符串》在Java中,由于字符串可能包含多字节字符,直接按字节长度截取可能会导致乱码或截取不准确的问题,下面我们就来看看几种按字节长度截取字符串的方法吧... 目录方法一:使用String的getBytes方法方法二:指定字符编码处理方法三:更精确的字符编码处理使用示例注意事项方

Python中pywin32 常用窗口操作的实现

《Python中pywin32常用窗口操作的实现》本文主要介绍了Python中pywin32常用窗口操作的实现,pywin32主要的作用是供Python开发者快速调用WindowsAPI的一个... 目录获取窗口句柄获取最前端窗口句柄获取指定坐标处的窗口根据窗口的完整标题匹配获取句柄根据窗口的类别匹配获取句

Java数组初始化的五种方式

《Java数组初始化的五种方式》数组是Java中最基础且常用的数据结构之一,其初始化方式多样且各具特点,本文详细讲解Java数组初始化的五种方式,分析其适用场景、优劣势对比及注意事项,帮助避免常见陷阱... 目录1. 静态初始化:简洁但固定代码示例核心特点适用场景注意事项2. 动态初始化:灵活但需手动管理代

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a

shell编程之函数与数组的使用详解

《shell编程之函数与数组的使用详解》:本文主要介绍shell编程之函数与数组的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录shell函数函数的用法俩个数求和系统资源监控并报警函数函数变量的作用范围函数的参数递归函数shell数组获取数组的长度读取某下的

MySQL高级查询之JOIN、子查询、窗口函数实际案例

《MySQL高级查询之JOIN、子查询、窗口函数实际案例》:本文主要介绍MySQL高级查询之JOIN、子查询、窗口函数实际案例的相关资料,JOIN用于多表关联查询,子查询用于数据筛选和过滤,窗口函... 目录前言1. JOIN(连接查询)1.1 内连接(INNER JOIN)1.2 左连接(LEFT JOI