优选算法：长度最小的子数组（滑动窗口）

Yuzuriha

发布于 2026-01-14 15:55:11

440

文章被收录于专栏：Linux网络Linux网络

题目详情：. - 力扣（LeetCode）

一. 题目解析

题意为：给一个数组，找其中元素相加>=目标值的最小子数组（子数组是连续的）

二. 算法分析

首先我们第一次看到这个题，第一想法肯定是暴力解法。既两个for循环暴力相加来判断，毫无疑问暴力解法肯定会超时，所以我们是算法正是基于暴力解法进行优化的

首先，我们还是定义两个指针left right 进行搜索然后相加，然后比较。这听起来好像和暴力解法没区别吧？接下来这个细节将是最大的区别：

如图，当left，right找到了大于等于目标值的情况，先记录长度。然后作为暴力解法的话就是，left++，right=left+1。这里的话仔细看我们会发现没必要，当大于等于目标和时，我们只需要移动left ，然后判断移动后的结果：如果仍是大于等于目标值，记录长度，left++。如果小于目标值则移动right，知道再次遇到大于目标和的情况再次进行判断

三. 代码实现

class Solution {
public:
    //滑动窗口：利用单调性+两个同向指针（指针不回退）时使用滑动窗口
    int len = INT_MAX;
    int minSubArrayLen(int target, vector<int>& nums)
    {
        int left = 0, right = 0;
        int sum = 0;
        for (; right < nums.size();right++)
        {
            sum += nums[right];
            while (sum >= target)
            {
                len = min(len, right - left + 1);
                sum -= nums[left++];
            }
        }
        return len == INT_MAX ? 0 : len;
    }
};