209. 长度最小的子数组

Problem: 209. 长度最小的子数组

思路

一开始是暴力算法,两个循环来找最小长度,超时

使用滑动窗口的思想,更新窗口窗头和窗尾的值即可

解题方法

left指向窗头,right指向窗尾,窗尾从头遍历到尾,达到target后更新窗头

脑瘫的错误

sum += nums[right];此处更新的是窗尾,我错误写成sum += nums[left];

int sum,left,subLen = 0;这样初始化在leetcode中报错不知道为什么

复杂度

• 时间复杂度:

$O(n)$

• 空间复杂度:

$O(1)$

Code

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int result = INT32_MAX;
        int sum = 0,left = 0,subLen = 0;
        for(int right = 0; right < nums.size(); right++){ //窗尾前移
            sum += nums[right];
            while(sum >= target) {
                subLen = right - left + 1;
                result = subLen < result ? subLen : result;
                sum -= nums[left];
                left ++;                                  //窗头前移
            }
        }
        return result == INT32_MAX ? 0 :result;
    }
};