LeetCode 209 - 长度最小的子数组（滑动窗口法）

题目描述

给定一个含有 n 个正整数的数组和一个正整数 target，我们要找出该数组中满足其总和大于等于 target 的长度最小的子数组，即子数组 [nums_left, nums_right]，并返回其长度。如果不存在符合条件的子数组，返回 0。

解题思路

我们可以使用滑动窗口解决这道问题。初始化左指针 start 和右指针 end 为 0，一个变量 min_length 记录最小长度，一个变量 sum 记录当前窗口内的和。然后我们不断移动右指针 end ，直到窗口内的和大于等于 target，然后将左指针 start 右移，缩小窗口长度，更新最小长度。重复这个过程，直到右指针到达数组末尾。

算法实现

C++实现

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

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组的长度。我们最多遍历每个元素两次，即左指针和右指针各一次。
• 空间复杂度：O(1)。

总结

本题利用滑动窗口技巧，高效地解决了求解满足条件的最小子数组长度的问题。通过维护一个窗口保证窗口内的和大于等于 target，不断更新最小长度，最终得到最小满足条件的子数组长度。

希望以上内容能帮助你更好地理解 LeetCode 209 长度最小的子数组问题。如果有任何疑问，欢迎留言讨论。