关于leetcode:每日一练45长度最小的子数组

title: 每日一练（45）：长度最小的子数组

categories:[剑指 offer]

tags:[每日一练]

date: 2022/04/19

每日一练（45）：长度最小的子数组

给定一个含有 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] <= 105

起源：力扣（LeetCode）

链接：https://leetcode-cn.com/probl…

办法一：队列模仿滑动窗口

思路剖析

应用队列模仿滑动窗口，并应用一个 sum 记录队列内数的和，因为数的大小有别，所以这里应用 while 来推出队列中的数

int minSubArrayLen(int target, vector<int>& nums) {
    int ans = INT_MAX, sum = 0;
    queue<int> que;
    for (auto &n : nums) {
        sum += n;
        que.push(n);
        while (sum >= target) {ans > que.size() ? ans = que.size() : ans;
            sum -= que.front();
            que.pop();}
    }
    return ans == INT_MAX ? 0 : ans;
}

办法二：双指针

思路剖析

定义两个指针 i 和 j 指针，将区间 [j,i] 看成滑动窗口，那么两个指针就别离示意滑动窗口的开始地位和完结地位，同时咱们再保护一个 sum 变量用来存贮区间 [j,i] 间断数组的和。如果以后滑动窗口保护的区间和 sum 大于等于 target，就阐明以后的窗口是可行的，可行中的长度最短的滑动窗口就是答案

int minSubArrayLen(int target, vector<int>& nums) {
    int res = INT_MAX, sum = 0;
    for (int i = 0, j = 0; i < nums.size(); i++) {sum += nums[i];// 向右扩大窗口
        while (sum - nums[j] >= target) {// 向左膨胀窗口
            sum -= nums[j++];
        } 
        if (sum >= target) {// 区间更新
            res = min(res, i - j + 1);
        }
    }
    return res == INT_MAX ? 0 : res;
}