[[双指针]]

长度最小的子数组

题目

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的==连续== 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

具体思路

滑动窗口的思想； 其实也是双指针，

• 当窗口不满足时，一直增加窗口长度，当窗口内的数满足假设要求，那么就可以统计当前的大小；
• 每一轮循环结束时，出掉窗口的左侧元素，并减少当前窗口大小；
• 每一轮迭代时，如果仍然满足要求才记录最优解；

具体代码

Java

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int res = Integer.MAX_VALUE;
        int left = 0;
        int sum = 0;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];

            while (target <= sum) {
                res = res > right - left + 1 ? right - left + 1 : res;
                sum -= nums[left];
                left++;
            }
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }
}

CPP

```cpp
include <iostream>
include <vector>
include <climits>
using namespace std;

class Solution
{
public:
    int minSubArrayLen(int target, vector<int> &nums)
    {
        int res = INT_MAX; // 初始化结果为最大整数值
        int subLen = 0; // 当前子数组的长度
        int fast = 0; // 快指针
        int slow = 0; // 慢指针
        int curTarget = 0; // 当前子数组的和

        for (; slow < nums.size(); slow++)
        {
            // 扩展窗口直到当前和大于等于目标值
            while (curTarget < target && fast < nums.size())
            {
                curTarget += nums[fast];
                fast++;
                subLen++;
            }
            // 如果当前和大于等于目标值，更新结果
            if (curTarget >= target)
                res = min(subLen, res);
            // 从左侧收缩窗口
            curTarget -= nums[slow];
            subLen--;
        }
        return res == INT_MAX ? 0 : res; // 如果没有找到符合条件的子数组，返回0
    }
};

int main()
{
    vector<int> nums = {2, 3, 1, 2, 4, 3};
    vector<int> nums1 = {1, 4, 4};
    vector<int> nums2 = {1, 1, 1, 1, 1, 1, 1, 1};
    vector<int> nums3 = {1, 2, 3, 4, 5};
    vector<int> nums4 = {5, 1, 3, 5, 10, 7, 4, 9, 2, 8};
    Solution s;
    cout << s.minSubArrayLen(7, nums) << endl; // 输出: 2
    cout << s.minSubArrayLen(4, nums1) << endl; // 输出: 1
    cout << s.minSubArrayLen(11, nums2) << endl; // 输出: 0
    cout << s.minSubArrayLen(11, nums3) << endl; // 输出: 3
    cout << s.minSubArrayLen(15, nums4) << endl; // 输出: 2
    return 0;
}