给定一个含有 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
进阶:
如果你已经实现 O(n) 时间复杂度的解法,请尝试设计一个 O(n log(n)) 时间复杂度的解法。
这道题是要找长度最小的连续子数组,可以使用滑动窗口,核心思路就是维护滑动窗口的两个数值,start 和 end:
class Solution {
public int minSubArrayLen(int s, int[] nums) {
int start = 0, end = 0, sum = 0, ans = Integer.MAX_VALUE;
while (end < nums.length && start < nums.length) {
// 滑动窗口,end,找到 [start, end] 的和>=s
while (end < nums.length && sum < s) {
sum += nums[end++];
// [start,end-1] 是可能的结果
if (sum >= s) {
ans = Math.min(ans, end - start);
}
}
// 滑动窗口,start,找到 [start, end] 的和<s
while (start < nums.length && sum >= s) {
sum -= nums[start++];
// [start-1,end] 是可能的结果
if (sum < s) {
ans = Math.min(ans, end - start + 1);
}
}
}
return ans == Integer.MAX_VALUE ? 0 : ans;
}
}
项目 GitHub LeetCode 全解,欢迎大家 star、fork、merge,共同打造最全 LeetCode 题解!
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。