Leetcode 209. 长度最小的子数组 双指针
2021-05-02 16:29
标签：进阶 subarray bsp public code 存在 bar solution https 地址 https://leetcode-cn.com/problems/minimum-size-subarray-sum/ 解答 算法1 如果和小于标准 则尝试扩大窗口 r++ Leetcode 209. 长度最小的子数组 双指针 标签：进阶 subarray bsp public code 存在 bar solution https 原文地址：https://www.cnblogs.com/itdef/p/13202198.html给定一个含有 n 个正整数的数组和一个正整数 s ，
找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。
如果不存在符合条件的连续子数组，返回 0。
示例:
输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。
进阶:
如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。
双指针遍历窗口 如果和大于等于标准 则进行长度统计 然后尝试缩小该窗口 l++class Solution {
public:
int minSubArrayLen(int s, vectorint>& nums) {
int l = 0; int r = 0;
if (nums.size() == 0) return 0;
int sum = nums[l];
int ans = 999999;
while (1) {
while (sum >= s) {
ans = min(ans, r - l + 1);
sum -= nums[l++];
if (l > r) break;
}
while (sum s) {
r++;
if (r >= nums.size()) break;
sum += nums[r];
}
if (l > nums.size() || r > nums.size()) break;
}
if (ans == 999999) ans = 0;
return ans;
}
};
文章标题：Leetcode 209. 长度最小的子数组 双指针
文章链接：http://soscw.com/index.php/essay/81410.html