力扣题目

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

进阶：

如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。
通过次数471,456提交次数993,416

我只会O(n^2)的算法哈哈哈哈，哎呀赶紧去学滑动窗口去~，我发现前缀和还挺实用。

暴力代码：前缀和数组

class Solution {
public:int minSubArrayLen(int target, vector& nums) {/** 滑动窗口在算法基础课讲过，但是不会啦，那当时没学透，再学即可* 暴力做法：前缀和~*/vector prefix_sum(nums.size(), 0);prefix_sum[0] = nums[0];// 计算前缀和for (int i = 1; i < nums.size(); i ++ ) prefix_sum[i] = prefix_sum[i - 1] + nums[i];// for (int i = 0; i < nums.size(); i ++ )//     cout << "前缀和为：" << prefix_sum[i] << " ";// 枚举长度1、2、3...n的窗口长度，一次次遍历for (int length = 1; length <= nums.size(); length ++ ) {// cout << "####枚举长度为：" << length << endl;for (int i = length - 1; i < nums.size(); i ++ ) {int l = i + 1 - length - 1, sub_sum;  // 左边界，即要减去的这部分的尾巴if (l == -1) sub_sum = 0;   // 要减去的前部分else sub_sum = prefix_sum[l];// 开始判断当前长度是否存在满足 target的连续序列// cout << "####当前长度下的连续和为：" << prefix_sum[i] - sub_sum << endl;if (prefix_sum[i] - sub_sum >= target) return length;}}return 0;}
};

提交：TLE

长度最小的子数组
提交记录
18 / 20 个通过测试用例
状态：超出时间限制
提交时间：几秒前

AC代码，思路来自卡哥(代码提前看了几眼，那代码估计先入为主，代码也来自卡哥)，传送门：代码随想录

class Solution {
public:int minSubArrayLen(int target, vector& nums) {/*** 卡哥讲的滑动窗口思想我目前理解就是双指针咯* 本来暴力解法是：for循环枚举起点+for循环枚举终点* 优化成 1个for循环枚举终点即可* 什么情况后移终点？ 当区间和不够，那起点呢？区间和太大。*/int minLength = 1e6;    // 题目给定最长就1e5int start_index = 0;long long sum = 0;  // 最大为1e10for (int end_index = 0; end_index < nums.size(); end_index ++ ) {sum += nums[end_index]; // 终点后移一位，区间和就加上一个数while (sum >= target) {minLength = min(minLength, end_index - start_index + 1);  // 更新最短长度// cout << minLength << " 起点，终点为：[" << start_index << "，" << end_index << "]" << endl;// 不用再后移终点了，开始后移起点，缩小区间sum -= nums[start_index];   // 减少起点那个数,接下去再判断一次是不是大于target，是则继续缩小start_index ++ ;    // @@@这里格外注意，先减sum，再移动，不然减错数}// 不够，则后移终点,进行end_index ++ }if (minLength == 1e6) minLength = 0;return minLength;   // 如果是无解，那就是返回0，OK的}
};