P4203. 寻找连续区间

解题思路

本题的数据量为 10^5，所以使用 O(n²) 的暴力解将无法通过所有用例。要思考时间复杂度更低的算法。

前缀和思路

题目要求求连续区间的和，很容易想到使用 前缀和 的思路来解决。

先求出前缀和数组，如对示例一求出 [3, 4, 7] 的前缀和数组为 pre_sum_list = [0, 3, 7, 14]。

由于原数组中每一个元素均为 非负整数，故前缀和数组一定是一个 非递减数组。

对于 pre_sum_list 中的每一个元素 pre_sum_list[i]，我们要找到索引 j（i < j）。j 是满足 pre_sum_list[j] - pre_sum_list[i] >= target 的第一个索引。此时任意比 j 大的索引 k，都能使得 pre_sum_list[k] - pre_sum_list[i] >= target 成立，即区间 [i, k] 是一个符合要求的区间。

由于前缀和数组是一个 非递减数组，j 的寻找可以很容易地使用 二分查找 来完成。

假设 j 已经求出，那么对于 i 而言，一共存在 n + 1 - j 个这样的区间，满足连续区间和大于等于 target。将所有 i 对应的 n + 1 - j 计算并求和，即可以得到答案。

不定滑窗思路

计算非负数组的连续子数组和的问题，也很容易想到使用 滑动窗口 的算法来解决。

但是正向的计算并不容易，因为假设我们可以计算出某个窗口的和大于等于 target，这个窗口向左、向右延长的子数组和也都会大于 target，那么左右指针向右移动的条件就不明晰，不符合我们的 滑窗三问三答 解题思路。

正难反易，我们反过来考虑这个问题。

对于长度为 n 的数组，一共存在 n * (n + 1) // 2 个子数组。

这里使用的是 组合数学 的知识，数组 nums 的非空子数组可以用任意的 (i, j) 下标对来表示即 nums[i:j]。由于要求子数组非空，所以一定存在 0 <= i < j <= n 成立。下标对 (i, j) 的个数，就代表了非空子数组的个数。即一共有多少组下标对，就一共有多少个非空子数组。这其实等同于在 0 到 n 一共 n + 1 个数字中任意挑选出来 2 个数字的组合数，也就是 C(n+1, 2)。

知道 nums 所有的子数组的个数有什么用呢？显然我们存在以下数学关系：

所有子数组的数目 = 子数组和大于等于 target 的子数组数目 + 子数组和小于 target 的子数组数目

所以，如果我们能够计算得到一共存在多少个小于 target 的子数组和，那么就可以反推出答案了。

在传统的滑窗题目中，题目通常会这样设问：寻找最长的连续子数组的长度，其子数组和小于 target。

我们先来解决这个传统的滑窗问题。这件事可以直接使用 滑窗三问三答 来解决，非常容易解决。

现在我们的问题转化为，怎么将上述 滑窗三问三答 中的 A3，修改为计算数组和小于 target 的子数组数目。

举一个例子来说明这个问题。对于下列例子：

在进行 A3 过程的时候，我们会得到以下的窗口：

这些窗口都是窗口和 严格小于 目标阈值 target = 10 的窗口。

我们会发现一个规律，这些窗口的 右闭边界 所取的数值，一定是按照原数组的顺序且依次排列的。

这个规律其实也很好解释，因为 right 的遍历就是从 0 开始到 n 结束依次进行的，且对于每一个 right，都一定会进行 A3 过程的更新。

对于一个窗口和小于目标阈值 target 的窗口 nums[left:right+1]，如果我们将其右闭边界固定，考虑它的所有包含右闭边界的子数组。一共存在 right - left + 1 个子数组。即：

譬如取 left = 1，right = 3 时，存在窗口 nums[left:right+1] = nums[1:4] = [2, 3, 4]，包含右闭边界 4 的子数组一共有 3 个，即：

由于所有元素都是 非负整数，因此这些包含了右闭边界的子数组的窗口和，一定也小于目标阈值 target。

所以，以某个 right 为右闭区间的窗口，能够带来的窗口和小于目标阈值 target 的子数组的数量（或者说贡献），就是这 right - left + 1 个子数组。

由于我们所有的窗口的右闭边界一定不相等，这样的做法能够保证我们所找到的窗口和小于目标阈值 target 的窗口数一定是 无遗漏且无重复 的。

对应到代码上，我们只需要修改上述代码中关于 ans 的定义和 A3 过程即可。即：

注意，我们的 A3 过程的代码调整为 ans -= (right - left + 1)，表示在所有非空子数组中，减去以 right 为右闭边界的所有目标和小于目标阈值 target 的数组数目。

最终退出循环后，ans 的结果就是所有窗口和大于等于目标阈值 target 的子数组数目了。

我们会发现，这种做法仍然沿用了 不定滑窗 的框架，时间复杂度比前缀和做法更加优秀，可以达到 O(N) 的时间复杂度。

还存在另一种滑窗解法，类似于 【不定滑窗】双机位 A/C - 优雅子数组 的思路。

当一个窗口 [left, right] 的和恰好小于 target 时，left 左边的所有指针 pre（即 pre < left 成立）和右边界 right 构成的区间 [pre, right] 的和大于等于 target。这意味着一共存在 left 个以 right 为右边界的区间，区间和大于 target。

因此我们可以把上述的 ans 初始化为 0，而 ans 的更新修改为 ans += left，也同样可以得到答案。即：

特殊情况判断

另外还有一种特殊情况需要讨论，target 的取值是可以为 0 的。

当 target 为 0 时，由于数组中所有的元素均为 正整数，因此任意的非空子数组的数组和均满足大于 target 的条件。由于一共存在 n * (n + 1) // 2 个子数组，在这种情况下直接返回 n * (n + 1) // 2 即为答案。

之所以要在这里进行 target = 0 的特殊情况判断，是因为无论是 前缀和 还是 不定滑窗 思路，当 target = 0 时，会把空数组（其和为 0）也认为是一种符合要求的情况，从而使得答案的值更大。

代码

解法一：前缀和解法