跳转至

209 长度最小的子数组

leetcode 链接

滑动窗口解法

需要强调的是,题目说了 nums 数组中的元素都是正数,有了这个前提才能使用滑动窗口算法,因为窗口扩大时窗口内元素之和必然增大,窗口缩小时窗口内元素之和必然减小。

如果 nums 数组中包含负数,则窗口扩大时元素和不见得就增大,窗口缩小时元素和不见得就减小,这种情况就不能单纯使用滑动窗口技巧了,可能需要混合动态规划和单调队列来做。

暴力做法(不能通过)

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int len = INT_MAX;
        for(int i = 0; i < nums.size(); i++){
            int sum = 0;
            for(int j = i; j < nums.size(); j++){
                sum += nums[j];
                if(sum >= target)
                    len = min(len, j - i + 1);
            }
        }
        return len == INT_MAX ? 0 : len;
    }
};

时间复杂度:\(O(n^2)\)

空间复杂度:\(O(1)\)

双指针法

class Solution {
public:
    const int INF = 0x3f3f3f3f;
    int minSubArrayLen(int target, vector<int>& nums) {
        int leftIndex = 0;
        int len = INF;
        int sum = 0;
        // 移动滑动窗口出口
        for(int rightIndex = leftIndex; rightIndex < nums.size(); rightIndex++){
            sum += nums[rightIndex];
            // 移动滑动窗口入口
            while(sum >= target){
                len = min(len, rightIndex - leftIndex + 1);
                // 关键步骤,不要忘记!
                sum -= nums[leftIndex];
                leftIndex++;
            }
        }
        return len == INF ? 0 : len;
    }
};

时间复杂度:O(n)

  • rightIndex移动了n次,leftIndex移动了n次,共移动2n次

空间复杂度:O(1)

以前写的版本

https://leetcode.cn/problems/minimum-size-subarray-sum/description/

题目关键在于:这个子数组是连续的

解法一:暴力枚举

先枚举子数组的起点,再往后枚举,满足sum >= target停止,计算子数组长度 j - i + 1

class Solution {
private:
    const int INF = 0x3f3f3f3f;
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        int ans = INF;
        for(int i = 0; i < n; i++){
            int sum = 0;
            for(int j = i; j < n; j++){
                sum += nums[j];
                if(sum >= target)
                    ans = min(ans, j - i + 1);
            }
        }
        if(ans == INF) 
            return 0;
        else
            return ans;
    }
};

复杂度分析

时间复杂度:\(O(n^2)\),其中 n 是数组的长度。需要遍历每个下标作为子数组的开始下标,对于每个开始下标,需要遍历其后面的下标得到长度最小的子数组。

空间复杂度:O(1)。

解法二: 前缀和 + 二分查找

解法一枚举起点之后又向后枚举了n个元素才找到sum >= target

由于本题限定了“正整数元素”,对于这种找到第一个满足sum >= target的元素,显然可以使用二分查找

我们的目标是sum >= target 而不是num >= target,因此需要一个数组记录每个元素作为末尾时的sum[i]

因此想到前缀和

class Solution {
private:
    const int INF = 0x3f3f3f3f;

public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        vector<int> s(n + 1);
        //  计算前缀和
        for (int i = 1; i <= n; i++) {
            // 这里原本是nums[i],但是nums和s的下标之间偏移了1
            s[i] = s[i - 1] + nums[i - 1];
        }
        int ans = INF;
        // 遍历起点,由于是遍历前缀和,所以下标可直接从1开始
        for (int i = 1; i <= n; i++) {
            // 我们要找到sum >= target
            // sum = s[idx] - s[i - 1]
            // 因此二分查找的目标为在数组s中找到大于等于target + s[i -
            // 1]的第一个元素
            int t = target + s[i - 1];
            auto it = lower_bound(s.begin(), s.end(), t);
            if (it != s.end()) {
                int idx = distance(s.begin(), it);
                ans = min(ans, idx - i + 1);
            }
        }
        return ans == INF ? 0 : ans;
    }
};

二分自己实现如下:

class Solution {
private:
    const int INF = 0x3f3f3f3f;

public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        vector<int> s(n + 1);
        //  计算前缀和
        for (int i = 1; i <= n; i++) {
            // 这里原本是nums[i],但是nums和s的下标之间偏移了1
            s[i] = s[i - 1] + nums[i - 1];
        }
        int ans = INF;
        // 遍历起点,由于是遍历前缀和,所以下标可直接从1开始
        for (int i = 1; i <= n; i++) {
            // 我们要找到sum >= target
            // sum = s[idx] - s[i - 1]
            // 因此二分查找的目标为在数组s中找到大于等于target + s[i - 1]的第一个元素
            int t = target + s[i - 1];
            int l = i, r = n;
            while(l < r){
                int mid = l + r >> 1;
                if(s[mid] >= t) r = mid;
                else l = mid + 1;
            }
            if(s[l] >= t)
                ans = min(ans, l - i + 1);
        }
        return ans == INF ? 0 : ans;
    }
};

解法三:移动窗口

由于题目的子数组是连续的序列,求sum >= target子数组长度最小值,实际上是要求子数组滑动时的最小值 >= target

想让子数组长度最小,意味着这个移动窗口的长度不定,因此移动窗口的头部也需要改变

加进一个元素

class Solution {
private:
    const int INF = 0x3f3f3f3f;
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        int start = 0, end = 0;
        int ans = INF;
        int sum = 0;
        while(end < n){
            sum += nums[end];
            while(sum >= target){
                ans = min(ans, end - start + 1);
                sum -= nums[start];
                start++;
            }
            end++;
        }
        return ans == INF ? 0 : ans;
    }
};

以上是双指针做法

如果套模板,使用队列解决,则是:

class Solution {
private:
    const int INF = 0x3f3f3f3f;
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        queue<int> q;
        int sum = 0;
        int ans = INF;
        for(int i = 0; i < n; i++){
            // 先加nums[i] 再对队头进行判断
            q.push(i);
            sum += nums[i];
            // 处理队头
            while(!q.empty() && sum >= target){
                sum -= nums[q.front()];
                ans = min(ans, q.back() - q.front() + 1);
                q.pop();
            }
        }
        return ans == INF ? 0 : ans;
    }
};

需要注意的是,队列的头是早加入的元素,尾是刚刚加入的元素,即头对应start,尾对应end