( 数组) 209. 长度最小的子数组——Leetcode每日一题
❓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 < = t a r g e t < = 1 0 9 1 <= target <= 10^9 1<=target<=109
- 1 < = n u m s . l e n g t h < = 1 0 5 1 <= nums.length <= 10^5 1<=nums.length<=105
- 1 < = n u m s [ i ] < = 1 0 5 1 <= nums[i] <= 10^5 1<=nums[i]<=105
进阶:
如果你已经实现 O(n)
时间复杂度的解法, 请尝试设计一个 O(nlog(n))
时间复杂度的解法。
💡思路:滑动窗口
定义两个指针 i
和 j
分别表示子数组(滑动窗口窗口)的开始位置和结束位置,维护变量 sum
存储子数组中的元素和(即从 nums[i]
到 nums[j]
的元素和)。
初始状态下, i
和 j
都指向下标 0
,sum
的值为 0
:
- 每一轮迭代,将
nums[j]
加到sum
,如果sum ≥ target
,则更新子数组的最小长度(此时子数组的长度是j − i 1
; - 然后将
nums[i]
从sum
中减去并将i
右移,直到sum < target
,在此过程中同样更新子数组的最小长度。 - 在每一轮迭代的最后,将
j
右移。
🍁代码:(Java、C )
Java
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int i = 0; // 滑动窗口起始位置
int sum = 0; // 滑动窗口数值之和
int ans = Integer.MAX_VALUE;
for(int j = 0; j < nums.length; j ){
sum = nums[j];//窗口内所有数的和
while(sum >= target) {//窗口内所有数的和大于target,则前移i(起始位置)
ans = ans < j - i 1 ? ans : j - i 1;
sum -= nums[i ];// 这里体现出滑动窗口的精髓之处,不断变更i(子序列的起始位置)
}
}
return ans == Integer.MAX_VALUE ? 0 : ans;
}
}
C
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int i = 0; // 滑动窗口起始位置
int sum = 0; // 滑动窗口数值之和
int ans = INT_MAX;
for(int j = 0; j < nums.size(); j ){
sum = nums[j];//窗口内所有数的和
while(sum >= target) {//窗口内所有数的和大于target,则前移i(起始位置)
ans = ans < j - i 1 ? ans : j - i 1;
sum -= nums[i ];// 这里体现出滑动窗口的精髓之处,不断变更i(子序列的起始位置)
}
}
return ans == INT_MAX ? 0 : ans;
}
};
🚀 运行结果:
🕔 复杂度分析:
- 时间复杂度: O ( n ) O(n) O(n),其中
n
为数组的长度。 - 空间复杂度: O ( 1 ) O(1) O(1)。
题目来源:力扣。
注: 如有不足,欢迎指正!
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhggiagh
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13