0209. Minimum Size Subarray Sum
===============================
题目信息
--------
:题号: 0209. 长度最小的子数组
:难度: Medium
:主题: 数组、滑动窗口、前缀和、二分查找
:原题: `LeetCode 0209 `_
:重点: 正数让窗口和单调变化,达到目标后必须连续收缩左端寻找最短长度
题目重述
--------
给定正整数 ``target`` 和只包含正整数的数组 ``nums``,找出元素和大于或等于 ``target`` 的
最短非空连续子数组,返回它的长度;若不存在满足条件的子数组,返回 ``0``。
``target`` 位于 ``[1, 10^9]``,数组长度位于 ``[1, 10^5]``,每个元素位于 ``[1, 10^4]``。子数组
必须使用连续位置,只返回长度,不要求返回起止下标。
自建示例
--------
最短窗口在中间:
.. code-block:: text
输入:target = 11,nums = [1, 4, 6, 5, 2]
输出:2
解释:[6,5] 的和为 11,长度为 2。
单个元素已经达标:
.. code-block:: text
输入:target = 4,nums = [1, 4, 4]
输出:1
整个数组也不达标:
.. code-block:: text
输入:target = 20,nums = [3, 5, 4, 2]
输出:0
C++ 实现
--------
.. code-block:: cpp
#include
#include
class Solution {
public:
int minSubArrayLen(int target, std::vector& nums) {
return slidingWindow(target, nums);
}
private:
int slidingWindow(int target, const std::vector& nums) {
long long sum = 0;
int left = 0;
int best = static_cast(nums.size()) + 1;
for (int right = 0; right < static_cast(nums.size()); ++right) {
sum += nums[right];
while (sum >= target) {
best = std::min(best, right - left + 1);
sum -= nums[left++];
}
}
return best == static_cast(nums.size()) + 1 ? 0 : best;
}
int prefixWithBinarySearch(int target, const std::vector& nums) {
int n = static_cast(nums.size());
std::vector prefix(n + 1, 0);
for (int index = 0; index < n; ++index) {
prefix[index + 1] = prefix[index] + nums[index];
}
int best = n + 1;
for (int right = 1; right <= n; ++right) {
long long limit = prefix[right] - target;
auto firstGreater = std::upper_bound(prefix.begin(), prefix.begin() + right, limit);
if (firstGreater != prefix.begin()) {
int left = static_cast(firstGreater - prefix.begin()) - 1;
best = std::min(best, right - left);
}
}
return best == n + 1 ? 0 : best;
}
};
题解
----
枚举区间会重复累加
~~~~~~~~~~~~~~~~~~~~
直接枚举起点 ``left``,向右扩展并累加,遇到和达标就更新答案;或者枚举所有起止位置再求和。
前者已经避免了重复计算同一起点的前缀,但最坏仍要为每个起点扫描很长后缀,时间为 ``O(n^2)``。
要找到最短窗口,不能只在第一次达标时停止:同一个右端下,删除若干左端元素后仍可能达标,
而窗口会更短。重复工作在于,枚举法反复从不同起点重新确认重叠区间的和。
正数提供边界单调性
~~~~~~~~~~~~~~~~~~~~
窗口 ``nums[left..right]`` 的元素全部为正,这一条件改变了搜索空间:
* 右端向右加入元素,窗口和只会增加;
* 左端向右删除元素,窗口和只会减少;
* 对固定右端,左端一旦右移到某个和不足的位置,再继续右移不可能重新达标。
因此右端每次加入一个元素后,只要窗口已经达标,就连续提交答案并收缩左端。第一次收缩后
变为不足时,本右端下的更小窗口全部不可行,可以把左端永久留在当前位置,等待下一个右端。
滑动窗口主解
~~~~~~~~~~~~~~
维护闭区间窗口 ``[left, right]``、其和 ``sum`` 和当前最短长度 ``best``:
1. 把 ``nums[right]`` 加入 ``sum``;
2. 只要 ``sum >= target``,用当前长度更新 ``best``;
3. 先记录,再减去 ``nums[left]`` 并右移 ``left``;
4. 和变小于目标后,右移 ``right`` 继续扩展。
“先记录再删除”不可交换:删除后得到的是更短窗口,原窗口若不先提交就会被永久丢掉。由于
所有元素为正,内层循环结束时,当前右端下没有遗漏的可行左端。
窗口不变量
~~~~~~~~~~~~
每轮外层循环完成加入操作后保持:
* ``sum`` 恰好等于当前 ``[left, right]`` 的元素和;
* ``left``、``right`` 只向右移动,窗口始终连续;
* ``best`` 是已经检查过的所有可行窗口长度的最小值;
* 已经移过的左端起点不可能在未来产生更短答案,因为它当时已经对应一个更早结束的可行窗口;
* 输入数组只读。
状态走读
~~~~~~~~
对 ``target = 7``、``nums = [2,3,1,2,4,3]``:
.. list-table::
:header-rows: 1
* - 加入位置
- 当前窗口和
- 连续收缩
- best
* - 0
- ``[2]``,2
- 不达标
- —
* - 1
- ``[2,3]``,5
- 不达标
- —
* - 2
- ``[2,3,1]``,6
- 不达标
- —
* - 3
- ``[2,3,1,2]``,8
- 提交 4,删 2 后和为 6
- 4
* - 4
- ``[3,1,2,4]``,10
- 提交 4;删 3 后 ``[1,2,4]`` 提交 3;再删 1 后和为 6
- 3
* - 5
- ``[2,4,3]``,9
- 提交 3;删 2 后 ``[4,3]`` 提交 2;再删 4 后和为 3
- 2
最终返回 2。每个右端下的连续收缩都在当前窗口仍达标时发生,因此没有错过中间的更短窗口。
前缀和与二分查找
~~~~~~~~~~~~~~~~~~
正数还使前缀和严格递增。令 ``prefix[i]`` 为前 ``i`` 个元素之和,区间 ``[left, right)``
达标等价于:
.. code-block:: text
prefix[right] - prefix[left] >= target
prefix[left] <= prefix[right] - target
固定 ``right`` 后,在前缀和的 ``[0, right)`` 中二分查找不大于
``prefix[right] - target`` 的最大下标;它给出当前右端的最靠右、也最短的可行左端。这个方案
把边界移动换成了有序数组查询,时间 ``O(n log n)``、空间 ``O(n)``。它满足题目追问,但主入口
选择滑动窗口,因为正数单调性可以把每次二分压缩为一次整体线性移动。
代码分析
~~~~~~~~
公共入口调用 ``slidingWindow``。``sum`` 使用 ``long long`` 保存窗口和;``best`` 以 ``n+1``
作为“尚未找到”哨兵,最后转为 0。右端加入后,内层 ``while`` 连续更新和删除左端,正是前文
中“同一右端不断寻找更短窗口”的状态转移。
``prefixWithBinarySearch`` 保留为另一条实现路径。它使用 ``upper_bound`` 找到第一个大于上限的
前缀位置,再退一格得到最大的合法 ``left``;前缀严格递增来自数组元素全为正。两个方法都不
修改输入,主解只保存四个标量,优先选择它是因为它完全消除了前缀数组和每次二分。
复杂度与边界
~~~~~~~~~~~~
滑动窗口中每个元素最多被右端加入一次、被左端删除一次,时间复杂度 ``O(n)``,额外空间
``O(1)``。前缀和二分法时间 ``O(n log n)``、空间 ``O(n)``。枚举起点的基线最坏为 ``O(n^2)``。
若整个数组和不足 ``target``,内层循环从不进入,哨兵转换为 0;若某个单元素已经达标,加入它
后立即记录长度 1。正数条件是滑动窗口正确性的必要结构;若允许负数,删除左端可能使和重新变大,
此单调收缩推导就不成立。