力扣209:长度最小的数组

2024-09-06 11:20
文章标签 数组 力扣 最小 长度 209

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

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

方法一:暴力(会超出时间限制)

思想,利用两个for循环,从前往后遍历数组,找出该数组中满足其总和大于等于 target 的长度最小的 子数组。

代码:

int minSubArrayLen(int s, int* nums, int numsSize) {if (numsSize == 0) {return 0;}int ans = INT_MAX;for (int i = 0; i < numsSize; i++) {int sum = 0;for (int j = i; j < numsSize; j++) {sum += nums[j];if (sum >= s) {ans = fmin(ans, j - i + 1);break;}}}return ans == INT_MAX ? 0 : ans;
}

时间复杂度O(n^2);空间复杂度O(1)

方法二:滑动窗口

思想:定义两个指针i和j,i表示起始位置,j表示结束位置。开始时,将最小距离设置成INT_MAX。开始时,i不变,从移动前往后移动j遍历数组,计算总和sum,当sum大于等于target时,将result更新为最小距离。并将sum减去nums[i],将i往后面遍历。最后去result的最小值。

输入:target = 7, nums = [2,3,1,2,4,3] 输出:2

开始i=0,j=0,nums[i]=num[j]=2;移动j,进行遍历。直到sum=[2+3+1+2]=8>target时,result=j-i+1=4;sum=[3+1+2]=6;i=1;继续往后遍历。

i=1,j=3,移动j,直到sum=[3+1+2+4]=10时,result=4,sum=[1+2+4]=7;i=2;继续往后遍历。

此时sum=7,result=j-i+1=3;sum=[2+4]=6,i=3;继续往后遍历。

i=3,j=4,移动j,直到sum=[2+4+3]=9时,result=j-i+1=3;sum=[4+3]=7,i=4;继续往后遍历。

此时sum=7,result=j-i+1=2;j无法再往后循环,最后最小值为result=2

int minSubArrayLen(int target, int* nums, int numsSize) {if (numsSize == 0) {return 0;}int result = INT_MAX;int i=0,j=0,sum=0;while(j<numsSize){sum += nums[j];while(sum >= target){result=fmin(result,j-i+1);sum -=nums[i];i++;}j++;}return result==INT_MAX ? 0:result;
}

时间复杂度O(n);空间复杂度O(1)

这篇关于力扣209:长度最小的数组的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/1141865

相关文章

Java中的数组与集合基本用法详解

《Java中的数组与集合基本用法详解》本文介绍了Java数组和集合框架的基础知识,数组部分涵盖了一维、二维及多维数组的声明、初始化、访问与遍历方法,以及Arrays类的常用操作,对Java数组与集合相... 目录一、Java数组基础1.1 数组结构概述1.2 一维数组1.2.1 声明与初始化1.2.2 访问

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案(推荐)2. 模糊匹配方案参数化查询示例使用场景建议性能优

关于集合与数组转换实现方法

《关于集合与数组转换实现方法》:本文主要介绍关于集合与数组转换实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、Arrays.asList()1.1、方法作用1.2、内部实现1.3、修改元素的影响1.4、注意事项2、list.toArray()2.1、方

MySQL 获取字符串长度及注意事项

《MySQL获取字符串长度及注意事项》本文通过实例代码给大家介绍MySQL获取字符串长度及注意事项,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql 获取字符串长度详解 核心长度函数对比⚠️ 六大关键注意事项1. 字符编码决定字节长度2

全面解析MySQL索引长度限制问题与解决方案

《全面解析MySQL索引长度限制问题与解决方案》MySQL对索引长度设限是为了保持高效的数据检索性能,这个限制不是MySQL的缺陷,而是数据库设计中的权衡结果,下面我们就来看看如何解决这一问题吧... 目录引言:为什么会有索引键长度问题?一、问题根源深度解析mysql索引长度限制原理实际场景示例二、五大解决

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

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

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

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

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

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

Java数组初始化的五种方式

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

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

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