Minimum Size Subarray Sum

209. 长度最小的子数组

分析

定义窗口区间：使用两个指针 i 和 j 表示滑动窗口的左右边界
窗口扩展：从左到右遍历数组，不断将元素加入当前窗口 sum += nums[i]
窗口收缩：
- 当窗口内的子数组和 target，尝试通过移动左指针 j 来缩小窗口，寻找更短的子数组
- 每次收缩时更新最小长度：res = min(res, i - j + 1)
返回结果：
- 如果没有找到符合条件的子数组，返回 0
- 否则，返回记录的最短长度

时间复杂度

时间复杂度 O(n)

空间复杂度

空间复杂度为 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


class Solution
{
public:
    int minSubArrayLen(int target, vector<int>& nums)
    {
        int res = INT_MAX;  // 初始化最小长度为无穷大
        int sum = 0;        // 窗口内子数组的和
        int j = 0;          // 左指针

        for (int i = 0; i < nums.size(); ++ i)  // 遍历数组
        {
            sum += nums[i];  // 扩大窗口（右指针右移）

            // 收缩窗口（左指针右移），直到和 < target
            while (sum - nums[j] >= target)
            {
                sum -= nums[j];  // 移除窗口左边的元素
                ++ j;             // 左指针右移
            }

            // 如果当前窗口和 >= target，更新最小长度
            if (sum >= target)
                res = std::min(res, i - j + 1);
        }

        // 如果没有符合条件的子数组，返回 0
        return res == INT_MAX ? 0 : res;
    }
};