209-长度最小的子数组

LeetCode

发布日期: 2021-06-05

LeetCode 209. Minimum Size Subarray Sum

Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray [numsl, numsl+1, ..., numsr-1, numsr] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Example 1:

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.

Example 2:

Input: target = 4, nums = [1,4,4]
Output: 1

method: 滑动窗口

sum是区间[j, i]的和

如果sum小于target，区间就扩大，即i++
如果sum大于target，区间就缩小，即j++

int minSubArrayLen(int target, vector<int>& nums) {
    int res = INT_MAX;
    int sum = 0;
    for (int i = 0, j = 0; i < nums.size(); i++) {
        sum += nums[i]; // 就硬加
        while (sum >= target) {     // 大于等于target就记录结果
            res = min(res, i - j + 1);  // [j, i]
            sum -= nums[j];
            j++;    // j移动，区间缩小
        }
    }
    return res == INT_MAX ? 0 : res;
}

时间复杂度：$O(n)$

LeetCode 862. 和至少为 K 的最短子数组

给你一个整数数组 nums 和一个整数 k ，找出 nums 中和至少为 k 的最短非空子数组，并返回该子数组的长度。如果不存在这样的子数组，返回 -1 。

子数组是数组中连续的一部分。

示例 1：

输入：nums = [2,-1,2], k = 3
输出：3

method: 前缀和+单调双端队列

prefix[i]记录的是0到i-1的前缀和

对于一个${\color{teal}{\mathrm{prefix}[y]}}$，我们希望找到一个${\color{teal}{\mathrm{prefix}[x]}}$，使得${\color{teal}{\mathrm{prefix}[y]-\mathrm{prefix}[x]\geq k}}$，并且使得${\color{teal}{y-x}}$最小

队列里面的前缀和是单调递增的（虽然存的是下标），如果${\color{teal}{\mathrm{prefix}[y]}}$比队列末尾的元素小，队列的末尾元素就要弹出，因为如果${\color{teal}{x_1 < x_2}}$，且${\color{teal}{\mathrm{prefix}[x_1] \geq \mathrm{prefix}[x_2]}}$，此时${\color{teal}{x_1}}$满足${\color{teal}{\mathrm{prefix}[y]-\mathrm{prefix}[x_1] \geq k}}$，那么${\color{teal}{x_2}}$肯定也满足${\color{teal}{\mathrm{prefix}[y]-\mathrm{prefix}[x_2] \geq k}}$，因为${\color{teal}{\mathrm{prefix}[x_2]}}$更小，并且${\color{teal}{x_2}}$更大，所以${\color{teal}{y-x_2}}$肯定小于${\color{teal}{y-x_1}}$，所以肯定要取${\color{teal}{x_2}}$，不会取${\color{teal}{x_1}}$，所以直接弹出
因为是递增的，所以来一个${\color{teal}{\mathrm{prefix}[y]}}$，就从队头开始找是否有${\color{teal}{\mathrm{prefix}[x]}}$，使得${\color{teal}{\mathrm{prefix}[y]-\mathrm{prefix}[x] \geq k}}$成立，如果第一个就不成立，后面肯定都不成立，所以不用找了，如果第一个成立，后面可能还有成立的，所以要继续找，所以用while，并且要将成立的${\color{teal}{\mathrm{prefix}[x]}}$弹出，因为即使后面又来了一个${\color{teal}{\mathrm{prefix}[y^{\prime}]}}$，${\color{teal}{y-x}}$肯定小于${\color{teal}{y^{\prime}-x}}$，所以直接弹出

int shortestSubarray(vector<int>& nums, int k) {
    int n = nums.size();
    vector<long> prefix(n + 1);
    for (int i = 1; i <= n; i++) {
        prefix[i] = prefix[i - 1] + nums[i - 1];
    }
    deque<int> dq;
    dq.push_back(0);
    int res = INT_MAX;
    for (int i = 1; i <= n; i++) {
        while (!dq.empty() && prefix[i] <= prefix[dq.back()]) {
            dq.pop_back();
        }
        while (!dq.empty() && prefix[i] - prefix[dq.front()] >= k) {
            res = min(res, i - dq.front()); // 找到了就更新结果 [dq.front(), i)
            dq.pop_front(); // 然后将队头元素弹出
        }
        dq.push_back(i);    // 队列里存的是下标
    }
    return res == INT_MAX ? -1 : res;
}