当前位置：首页 > article >正文

leetcode 209. 长度最小的子数组

article 2025/1/31 0:57:04

题目如下
在这里插入图片描述
数据范围

本题同样可以用不定长的滑动窗口来解决
1.维护变量sum来表示从左端点到右端点的和。
2.当sum满足条件时将左端点向右移动寻找最小子数组。(注意这里左端点不用向左移动即使后面sum不再满足条件,因为我们实际上找到的是从0开始到右端点的最小子数组了所以向左移动左端点是重复计算不需要)
3.移动右端点(实际上写进for循环就行 从0到n - 1)

通过代码

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