LeetCode 209：长度最小的子数组 ← 滑动窗口

【题目来源】
https://leetcode.cn/problems/minimum-size-subarray-sum/description/

【题目描述】
给定一个含有 n 个正整数的数组和一个正整数 target。
找出该数组中满足其总和大于等于 target 的长度最小的子数组，并返回其长度。如果不存在符合条件的子数组，返回 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<=10^9
1<=nums.length<=10^5
1<=nums[i]<=10^5

【算法分析】
● INT_MAX 和 INT_MIN 是 C++ 的两个宏，代表了整型变量能够存储的最大正整数和最小负整数，分别为 2147483647 和 -2147483648。INT_MAX 比十六进制数 0x3f3f3f3f 表示的数更大。

#include<bits/stdc++.h>
using namespace std;int main() {cout<<INT_MAX<<endl; //2147483647cout<<INT_MIN<<endl; //-2147483648return 0;
}

● 本代码运行后，需要按 Ctrl+Z 终止运行后，回车才能返回运行结果。
● 在常见的算法刷题网站中，算法题的提交有 ACM 模式与核心代码模式（以类中自定义函数的形式呈现）。比如，若以求两数之和的代码为例，ACM 模式与核心代码模式对应的代码分别如下所示。
（1）ACM 模式

#include<bits/stdc++.h>
using namespace std;int twoSum(int x,int y) {return x+y;
}int main() {int x,y;cin>>x>>y;cout<<twoSum(x,y)<<endl;return 0;
}/*
in:2 3
out:5
*/

（2）核心代码模式

class Solution {public:int twoSum(int x,int y) {return x+y;}
};

● 在 LeetCode 中，代码提交采用核心代码模式。故本例在 LeetCode 中的代码如下所示。

class Solution {public:int minSubArrayLen(int target, vector<int>& nums) {int n=nums.size();int sum=0, res=INT_MAX;for(int i=0, j=0; j<n; j++) {sum+=nums[j];while(sum>=target) {res=min(res, j-i+1);sum-=nums[i++];}}return res==INT_MAX?0:res;}
};

【算法代码】

#include<bits/stdc++.h>
using namespace std;int minSubArrayLen(int target,vector<int>& nums) {int n=nums.size();int sum=0,res=INT_MAX;for(int i=0,j=0; j<n; j++) {sum+=nums[j];while(sum>=target) {res=min(res,j-i+1);sum-=nums[i++];}}return res==INT_MAX?0:res;
}int main() {int target,x;cin>>target;vector<int> nums;while(cin>>x){nums.push_back(x);} cout<<minSubArrayLen(target,nums)<<endl;return 0;
}/*
in:
7
2 3 1 2 4 3out:
2
*/

【参考文献】
https://blog.csdn.net/qq_41094332/article/details/122973987
https://blog.csdn.net/DuanNaiLin/article/details/134340774
https://blog.csdn.net/code_peak/article/details/128435905