求满足特定条件的数组子数组数量的最优时间复杂度

首先把问题做等价转化：设数组总和为total，子数组和为S，题目要求的「子数组和大于子数组外元素和」等价于 S > total - S，进一步推导为 2*S > total（即子数组和大于总和的一半）。

最优时间复杂度取决于数组元素的性质，分两种情况讨论：

情况1：数组所有元素均为正数 #

此时可以用**滑动窗口（双指针）**实现O(n)的时间复杂度，这是该场景下的最优解：

• 由于元素全为正，窗口的和会随右指针右移单调递增，左指针可以同步右移缩小窗口，每个元素最多被左右指针各访问一次。
• 具体操作步骤：
  1. 计算数组总和total，目标阈值为target = total / 2。
  2. 初始化左指针left=0、当前窗口和current_sum=0、结果计数count=0。
  3. 遍历右指针right从0到数组末尾：
     • 将nums[right]加入current_sum。
     • 当current_sum > target时，说明所有以right结尾、起始位置在left到right之间的子数组都满足条件（共right - left + 1个），将该数量计入count；随后左移left并减去nums[left]，直到current_sum <= target。

以你给出的例子[24, 36, 21, 56, 3, 9, 75]为例，数组总和为224，目标阈值为112，用滑动窗口可以高效统计所有和大于112的子数组。

情况2：数组包含负数或零 #

此时滑动窗口不再适用（窗口和可能随右指针右移而减小），最优方法是前缀和+排序+二分查找，时间复杂度为O(n log n)：

• 先计算前缀和数组prefix，其中prefix[0]=0，prefix[i]表示数组前i个元素的和。
• 对于每个i，我们需要找到所有j < i使得prefix[i] - prefix[j] > target，即prefix[j] < prefix[i] - target。
• 维护一个有序的前缀和集合，遍历每个prefix[i]时，用二分查找快速统计符合条件的j的数量，再将当前prefix[i]加入有序集合。

总结 #

• 元素全为正：最优时间复杂度为O(n)
• 包含负数/零：最优时间复杂度为O(n log n)

内容的提问来源于stack exchange，提问作者Justin Young