Leetcode209. 长度最小的子数组

发布时间 2023-03-22 21:13:04作者: 章章_思游容

题目跳转链接

滑动窗口解法

代码随想录 209.长度最小的子数组

滑动窗口是一种基于双指针的算法,它可以用于解决一些数组/字符串的子元素问题,例如:找到最长的子数组、最小的子串等等。

滑动窗口算法的思路就是维护两个指针,一个左指针和一个右指针,它们之间的区间就是滑动窗口。我们需要根据题目要求不断调整这两个指针的位置,来达到求解问题的目的。

在本题中,我们需要找到数组中满足其和 ≥ target 的长度最小的连续子数组,那么我们就可以使用滑动窗口算法来解决这个问题。具体步骤如下:

  1. 初始化左指针 i 和右指针 j,它们初始值都为 0。
  2. 初始化滑动窗口的数值之和 sum,初始值为 0。
  3. 当 sum < target 时,右指针向右移动一位,将 nums[j] 加入到 sum 中。
  4. 当 sum >= target 时,记录当前子数组的长度 (j - i + 1),并更新最小值。
  5. 然后移动左指针 i,将 nums[i] 从 sum 中减去,继续判断 sum 是否大于等于 target。
  6. 重复步骤 3-5,直到 j 超过数组范围。

这个算法的核心就是维护一个滑动窗口,不断调整左右指针的位置,来达到求解问题的目的。我们可以把这个过程想象成在一个数组上滑动一个大小可变的窗口,每次根据窗口内的值来判断左右指针的移动方式。

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) 
    {
        int result=INT32_MAX;
        int sum=0;
        int i=0;
        int subLength=0;  //滑动窗口的长度

        for(int j=0;j<nums.size();j++)
        {
            sum+=nums[j];
            while(sum>=target)
            {
                subLength=(j-i+1);  //取子序列的长度
                result=result<subLength?result:subLength;
//跟踪这个子数组的长度。 只有在找到更短的子数组时,才会更新此长度。它将最小长度分配给result变量。
                sum-=nums[i++];
//5. 然后移动左指针 i,将 nums[i] 从 sum 中减去,继续判断 sum 是否大于等于 target。
//6. 重复步骤 3-5,直到 j 超过数组范围。
            }
        }
        // 如果result没有被赋值的话,就返回0,说明没有符合条件的子序列
        return result == INT32_MAX ? 0 : result;

    }
};