AlgoPressAppearance
0209-长度最小的子数组
https://leetcode.cn/problems/minimum-size-subarray-sum
给定一个含有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 <= 10^9
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^5
进阶：
- 如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。
思路1：暴力法
遍历到某个数之后，开始往后计算和，满足条件的时候，计算长度
参考代码
csharp
public class Solution {
public int MinSubArrayLen(int s, int[] nums)
{
int n = nums.Length;
if (n == 0)
{
return 0;
}
int ans = int.MaxValue;
for (int i = 0; i < n; ++i)
{
int sum = 0;
for (int j = i; j < n; ++j)
{
sum += nums[j];
if (sum >= s)
{
ans = Math.Min(ans, j - i + 1);
break;
}
}
}
return ans == int.MaxValue ? 0 : ans;
}
}
思路2:动态规划
动态规划，定义 dp[i] 表示从0开始到 i 的所有数字的和 所以当 dp[i] - dp[j] >= target 的时候，计算 i - j 并且缓存最小的值就是结果 从后往前遍历，当遇到满足条件的时候就可以退出当次循环，因为再往前，即便满足条件长度也大于当前的长度了。 注意：当dp[i]直接满足条件的时候，需要计算全部的长度，即 i+1
参考代码
csharp
public class Solution {
public int MinSubArrayLen(int target, int[] nums) {
int preSum = 0;
int minCount = int.MaxValue;
int[] dp = new int[nums.Length];
for(int i=0; i<nums.Length; i++){
preSum += nums[i];
dp[i] = preSum;
//计算前缀和差
if(dp[i] >= target){
minCount = Math.Min(minCount,i+1);
}
for(int j=i-1; j>=0;j--){
if(dp[i] - dp[j] >= target){
minCount = Math.Min(minCount,i-j);
break;
}
}
}
return minCount == int.MaxValue ? 0 : minCount;
}
}
参考代码：优化二分查找
因为数组是递增的，因此可以通过二分法查找满足条件的边界
csharp
public class Solution{
//找寻 target 的左边界
private int LowerBound(int[] arr, int left, int right, int target){
while(left < right){
int mid = left + (right - left) / 2;
if( arr[mid] < target){
left = mid + 1;
}
else{
right = mid;
}
}
return arr[left] >= target ? left : -1;
}
public int MinSubArrayLen(int target, int[] nums){
if(nums.Length == 0){
return 0;
}
int minCount = int.MaxValue;
int[] dp = new int[nums.Length+1];
//计算前缀和
//dp[0] 表示前0个数相加的和
//dp[1] 表示前1个数相加的和
for(int i=1; i<=nums.Length; i++){
dp[i] = dp[i-1] + nums[i-1];
}
for(int i=1;i<=nums.Length;i++){
int t = target + dp[i-1];
int bound = LowerBound(dp,i,nums.Length,t);
//Console.WriteLine("bound={0}",bound);
if(bound != -1){
minCount = Math.Min(minCount, bound - i + 1);
}
}
return minCount == int.MaxValue ? 0 : minCount;
}
}
思路3：滑动窗口
设置双指针 i,j 表示当前的窗口大小 i = 0 表示窗口的起始位置 j 从 0 开始往下遍历，遍历过程中统计 sum ，当发现 sum >= target 的时候我们就可以计算长度，并且存到变量中。 因为我们要求得是最短长度，所以我们可以开始调整左边界，即 i， 调整过程中减去 nums[i]，直到 sum < target
参考代码
csharp
public class Solution {
public int MinSubArrayLen(int target, int[] nums) {
int minCount = int.MaxValue;
int i = 0;
int sum = 0;
for(int j = 0; j < nums.Length; j++){
sum += nums[j];
while(sum >= target){
int len = j - i + 1;
minCount = Math.Min(minCount, len);
//此时可以缩短前面的值
sum -= nums[i];
i++;
}
}
return minCount == int.MaxValue ? 0 : minCount;
}
}