目录

前言

一、暴力求解

二、同向双指针（滑动窗口算法）

---

---

前言

题目链接：. - 力扣（LeetCode）

题目：

输入一个正整数组成的数组和一个正整数 k，请问数组中和大于或等于 k 的连续子数组的最短长度是多少？如果不存在所有数字之和大于或等于 k 的子数组，则返回 0。例如，输入数组 [5, 1, 4, 3]，k 的值为 7，和大于或等于 7 的最短连续子数组是 [4, 3]，因此输出它的长度 2。

分析：

子数组由数组中一个或连续的多个数字组成。一个子数组可以用两个指针表示。如果第 1 个指针 left 指向子数组的第 1 个数字，第 2 个指针 right 指向子数组的最后一个数字，那么子数组就是由这两个指针之间的所有数字组成的。

---

一、暴力求解

1. 先固定指针 left（最开始指向数组中的第 1 个元素）。

2. 然后从 left 开始不断向右移动指针 right，直到两个指针之间的子数组中所有数字之和大于或等于 k（子数组的长度为 right - left + 1），或者 right 超出范围，即不存在和大于或等于 k 的子数组。

3. 如果不存在和大于或等于 k 的子数组，则说明已经尝试了所有的可能性，可以结束这个查找的过程了；否则 ++ left，然后重复步骤 1 和 2，直到 left 超出范围。

这种解法的时间复杂度是 O(n^2)。

当 left = 0 时，right 的最优解为 2（right >= 2 && right < 4，两个指针之间的子数组中所有数字之和大于或等于 k）；

当 left = 1 时，right 的最优解为 3；

当 left = 2 时，right 的最优解为 3；

当 left = 3 时，right 没有解。

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int n = nums.size();int minLen = n + 1;for (int left = 0; left < n; ++left){int sum = 0;for (int right = left; right < n; ++right){sum += nums[right];if (sum >= target){if (right - left + 1 < minLen)minLen = right - left + 1;break;}}if (sum < target)break;}return minLen == n + 1 ? 0 : minLen;}
};

---

二、同向双指针（滑动窗口算法）

可以对上述解法进行优化。指针 left 和 right 初始化的时候指向数组的第 1 个元素。

1. 不断向右移动指针 right，直到两个指针之间的子数组数字之和大于或等于 k（子数组的长度为 right - left + 1）。

2. 停止右移指针 right，转而不断向右移动指针 left，直到两个指针之间的子数组数字之和小于 k。注意：指针 left 每向右移动一步，如果两个指针之间的子数组数字之和大于或等于 k，那么就要更新最短子数组的长度，这相当于利用了第 1 步产生的结果。

3. 重复步骤 1 和 2，直到 right 超出范围。

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int n = nums.size();int minLen = n + 1;int left = 0;int sum = 0;for (int right = 0; right < n; ++right){sum += nums[right];while (sum >= target){if (right - left + 1 < minLen)minLen = right - left + 1;sum -= nums[left];++left;}}return minLen == n + 1 ? 0 : minLen;}
};

尽管上述代码中有两个嵌套的循环，该解法的时间复杂度仍然是 O(n)。这是因为在这两个循环中，变量 left 和 right 都是只增加不减少，变量 right 从 0 增加到 n - 1，变量 left 从 0 最多增加到 n - 1，因此总的执行次数是 O(n)。