和大于等于target的最短子数组

给定一个含有 n 个正整数的数组和一个正整数 target ，

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。

如果不存在符合条件的子数组，返回 0 。

1.静态滑动窗口1

遍历滑动窗口大小，每次for循环滑动窗口大小值固定，每次对滑动窗口中的内容进行求和，尝试更新答案，时间超时：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int flag = 0;
        int ans = nums.size();
        //遍历滑动窗口的大小
        for (int len = 1; len <= nums.size(); ++len) {
            for (int i = 0, j = i + len; j <= nums.size(); ++i, ++j) {
                int sum = 0;
                for (int k = i; k < j; ++k) sum += nums[k];
                if (sum >= target && len <= ans) {
                    ans = len;
                    flag = 1;
                }
            }
        }
        if (!flag) return 0;
        return ans;
    }
};

2.静态滑动窗口2

遍历滑动窗口大小，每次for循环滑动窗口大小值固定，

维护一个sum值 进行加入与减出，每次窗口移动加入与减出边界值，尝试更新答案，时间超时（使用Java语言可以成功通过）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int flag = 0;
        int ans = nums.size();
        //遍历滑动窗口的大小
        for (int len = 1; len <= nums.size(); ++len) {
            int sum = 0;
            for (int i = 0; i < len; ++i) sum += nums[i];
            if (sum >= target && len <= ans) { ans = len; flag = 1;}
            for (int i = 0, j = i + len; j < nums.size(); ++i, ++j) {
                sum -= nums[i];
                sum += nums[j];
                if (sum >= target && len <= ans) {
                    ans = len;
                    flag = 1;
                }
            }
        }
        if (!flag) return 0;
        return ans;
    }
};

3.动态滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//写法1
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int ans = INT32_MAX;
        int sum = 0;
        for (int i = 0, j = 0; j < nums.size(); ++j) {
            sum += nums[j];
            while (sum >= target) {
                ans = min((j - i + 1), ans);
                sum -= nums[i];
                i++;
            }
        }
        return ans == INT32_MAX ? 0 : ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//写法2 将ans的更新操作写在while循环中可降低程序执行时间！
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int sum = 0;
        int ans = INT32_MAX;
        for (int i = 0, j = 0; j < nums.size(); ++j) {
            int flag = 0;
            sum += nums[j];
            while (sum >= target) {
                flag = 1;
                sum -= nums[i];
                i++;
            }
            if (flag) ans = min((j - i + 2), ans);
        }
        return ans == INT32_MAX ? 0 : ans;
    }
};

4.前缀和+二分查找

参考：https://leetcode.cn/problems/2VG8Kg/solutions/1764854/by-ac_oier-vw5r/

由 nums[i] 的数据范围为[1,105]，可知前缀和数组满足单调递增，可以使用二分查找

  1. 先预处理出前缀和数组 sum（前缀和数组下标默认从1开始），对于每个nums[i]其对应的前缀和值为 s=sum[i+1]
  2. 将 nums[i] 视为子数组的右端点，
  3. 问题转换为：在前缀和数组下标 [0,i] 范围内找到满足值小于等于 s−t 的最大下标，充当子数组左端点的前一个值
  4. 利用前缀和数组的单调递增，该操作可使用二分来做
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int size = nums.size();

        //1.前缀和数组初始化
        vector<int> prefix(size + 1, 0);
        for (int i = 1; i <= size; ++i) prefix[i] = prefix[i - 1] + nums[i - 1];

        //2.利用upper_bound进行查找
        int ans = INT32_MAX;
        for (int i = 1; i <= size; ++i) {
            int temp = target + prefix[i - 1];
            int j = lower_bound(prefix.begin(), prefix.end(), temp) - prefix.begin();
            if (lower_bound(prefix.begin(), prefix.end(), temp) != prefix.end())ans = min(ans, j - i + 1);
            //ans = min(ans, j - i + 1);
        }
        return ans == INT32_MAX ? 0 : ans;
    }
};