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

长度最小的子数组（滑动窗口）

article 2024/11/5 20:44:05

给定一个含有 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 <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 104

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left = 0, sum = 0;
        int n = nums.size();
        int min_length = INT_MAX;

        for (int right = 0; right < n; ++right) {
            sum += nums[right];

            while (sum >= target) {
                min_length = min(min_length, right - left + 1);
                sum -= nums[left];
                left++;
            }
        }

        return min_length == INT_MAX ? 0 : min_length;
    }
};

由于子数组是数组中连续的非空元素序列。这意味着，在一个数组中选择的元素必须彼此相邻，才能构成一个子数组。

滑动窗口是一种在数组或字符串等线性数据结构上高效地解决子区间问题的方法。问题的核心在于找到一个和大于等于 target 的最短连续子数组。为了高效地找到这个子数组，我们可以使用滑动窗口

初始化定义 left 指针为窗口的左边界，right 指针为窗口的右边界。用 sum 变量记录窗口内元素的和，用 min_length 变量存储满足条件的最小子数组长度。

用 right 指针遍历数组，将每个元素值加入 sum。这样做的目的是逐步扩大窗口，尝试找到满足条件（sum >= target）的子数组

当 sum 大于等于 target 时，说明当前窗口已经符合条件。此时更新 min_length

为了找到更小的满足条件的子数组长度，我们尝试通过增加 left 来缩小窗口。将 nums[left] 从 sum 中减去，然后将 left 向右移动一格，缩小窗口范围。不断重复该过程，直到 sum 小于 target 为止。

遍历结束后，min_length 会记录符合条件的最小长度。如果 min_length 仍为初始化值，说明没有满足条件的子数组，返回 0；

实例：

target = 7
nums = [2, 3, 1, 2, 4, 3]

初始化变量：

left = 0，sum = 0，min_length = INT_MAX

遍历数组，右指针 right 从 0 到 nums.size() - 1：

第一步：`right = 0`

将 nums[0] = 2 加到 sum 中，sum = 2。
sum < target，不满足条件，继续扩展窗口。

第二步：`right = 1`

将 nums[1] = 3 加到 sum 中，sum = 2 + 3 = 5。
sum < target，继续扩展窗口。

第三步：`right = 2`

将 nums[2] = 1 加到 sum 中，sum = 5 + 1 = 6。
sum < target，继续扩展窗口。

第四步：`right = 3`

将 nums[3] = 2 加到 sum 中，sum = 6 + 2 = 8。
sum >= target，窗口满足条件，计算当前窗口长度 right - left + 1 = 3 - 0 + 1 = 4。
更新 min_length = min(INT_MAX, 4) = 4。
尝试收缩窗口：将 nums[left] = 2 从 sum 中减去，sum = 8 - 2 = 6，然后 left 向右移动一格，left = 1。

第五步：`right = 3`，`left = 1`

此时 sum = 6 < target，不满足条件，继续扩展窗口。

第六步：`right = 4`

将 nums[4] = 4 加到 sum 中，sum = 6 + 4 = 10。
sum >= target，窗口满足条件，计算当前窗口长度 right - left + 1 = 4 - 1 + 1 = 4。
min_length 保持不变，因为已经是 4。
尝试收缩窗口：将 nums[left] = 3 从 sum 中减去，sum = 10 - 3 = 7，left 右移一格，left = 2。