解题思路
数组里全是正整数,要找总和 ≥target 的最短连续段。没有就输出 0。
- 用滑动窗口:右端点 r 从左到右扫,把 numsr 加进窗口和 s。
- 一旦 s≥target,就尝试把左端点 l 右移。因为元素为正,左移只会让 s 变小,所以可以一直缩,直到窗口刚好还满足(或再也满足不了)。每次满足时用 r−l+1 更新最短长度。
- 正数保证窗口具有单调性:更长的段和一定更大,因此每个端点最多进出一次,总复杂度是 O(n)。
- 若扫完最短长度仍是哨兵(例如 n+1),说明整段和都小于 target,答案为 0。
- n≤105,暴力枚举左右端点是 O(n2),过不了。常见假解:找到第一段满足的就停(不一定最短);或者把「最长公共子序列」那套 DP 搬过来。