LeetCode 327. 区间和的个数
题目描述
题意分析
统计有多少个非空连续子数组，其元素和落在闭区间
[lower, upper]内。元素可以为负，区间变长时和不一定变大，因此不能直接用普通滑动窗口；相同的区间和出现在不同位置时，要分别计数。
解法：前缀和 + 归并排序
核心思路
[!blue]
定义
pre[t]为前t个数的和，pre[0] = 0。子数组nums[l..r-1]的和为pre[r] - pre[l]，其中l < r。问题转为统计有序下标对，使较晚前缀减较早前缀的差落在给定范围内；保留空前缀才能统计从数组开头出发的子数组。按原始前缀下标把区间分成左右两半。合法配对要么完全在左半，要么完全在右半，要么较早位置在左、较晚位置在右。递归处理前两类，并让各半按前缀值排序；第三类只需跨两半计数，因为左半的原始位置一定早于右半。组内排序不会改变这个先后关系，但不能提前把整个数组混合排序。
对左半的某个前缀值
x，需要右半值y满足lower <= y - x <= upper。右半已经有序，用i找第一个差值不小于lower的位置，用j找第一个差值大于upper的位置，合法候选就是半开区间[i, j)，贡献j - i个配对。两端的推进条件分别是< lower和<= upper，才能同时包含答案范围的两个端点。左半也已排序，
x逐渐增大时，右半所需值的范围[x + lower, x + upper]只会向右移动，因此两个指针都无需回退或重置。每层中左半扫描一次，两个指针各最多扫过右半一次，跨组计数只需线性时间。计数完成后再归并两半，为父层提供有序值。任意一对前缀只会在它们首次分处左右两半的那层被跨组计数，与两侧递归结果相加既不重复也不遗漏。相同前缀值仍保留各自出现次数，不能去重。
单个前缀无法组成非空子数组，是递归返回 0 的边界。前缀累计和及差值可能超过
int，使用long或int64；题目保证最终计数可放入 32 位整数，因此返回值仍使用int。
解题步骤
- 创建长度为
n + 1的宽整数前缀和数组，保留初始的 0。- 对半开区间
[left, right)递归；长度不超过 1 时返回 0。- 递归统计两半，使它们分别有序，再用双指针统计跨半区间的合法差值。
- 将两半归并并写回原区间，返回左半、右半和跨半计数之和。
代码实现
class Solution {
public int countRangeSum(int[] nums, int lower, int upper) {
long[] pre = new long[nums.length + 1];
for (int i = 0; i < nums.length; i++) {
pre[i + 1] = pre[i] + nums[i];
}
return mergeCount(pre, 0, pre.length, lower, upper);
}
private int mergeCount(long[] pre, int left, int right, int lower, int upper) {
if (right - left <= 1) {
return 0;
}
int mid = left + (right - left) / 2;
int count =
mergeCount(pre, left, mid, lower, upper)
+ mergeCount(pre, mid, right, lower, upper);
// 两半已分别有序，左右仍代表原始前后位置组
int i = mid;
int j = mid;
for (int l = left; l < mid; l++) {
// 左边界停在首个差值达到下界的位置
while (i < right && pre[i] - pre[l] < lower) {
i++;
}
// 右边界停在首个差值超过上界的位置
while (j < right && pre[j] - pre[l] <= upper) {
j++;
}
count += j - i;
}
// 先计数再归并，父层继续使用有序前缀值
long[] merged = new long[right - left];
int p1 = left;
int p2 = mid;
int p = 0;
while (p1 < mid && p2 < right) {
if (pre[p1] <= pre[p2]) {
merged[p++] = pre[p1++];
} else {
merged[p++] = pre[p2++];
}
}
while (p1 < mid) {
merged[p++] = pre[p1++];
}
while (p2 < right) {
merged[p++] = pre[p2++];
}
System.arraycopy(merged, 0, pre, left, merged.length);
return count;
}
}
func countRangeSum(nums []int, lower int, upper int) int {
pre := make([]int64, len(nums)+1)
for i := 0; i < len(nums); i++ {
pre[i+1] = pre[i] + int64(nums[i])
}
return mergeCount(pre, 0, len(pre), int64(lower), int64(upper))
}
func mergeCount(pre []int64, left int, right int, lower int64, upper int64) int {
if right-left <= 1 {
return 0
}
mid := left + (right-left)/2
count := mergeCount(pre, left, mid, lower, upper) + mergeCount(pre, mid, right, lower, upper)
// 两半已分别有序，左右仍代表原始前后位置组
i, j := mid, mid
for l := left; l < mid; l++ {
// 左边界停在首个差值达到下界的位置
for i < right && pre[i]-pre[l] < lower {
i++
}
// 右边界停在首个差值超过上界的位置
for j < right && pre[j]-pre[l] <= upper {
j++
}
count += j - i
}
// 先计数再归并，父层继续使用有序前缀值
merged := make([]int64, right-left)
p1, p2, p := left, mid, 0
for p1 < mid && p2 < right {
if pre[p1] <= pre[p2] {
merged[p] = pre[p1]
p1++
} else {
merged[p] = pre[p2]
p2++
}
p++
}
for p1 < mid {
merged[p] = pre[p1]
p1++
p++
}
for p2 < right {
merged[p] = pre[p2]
p2++
p++
}
copy(pre[left:right], merged)
return count
}
复杂度分析
- 时间复杂度：$O(n\log(n+1))$，
n为原数组长度，每层统计与归并合计为线性，共有对数层。- 空间复杂度：$O(n)$，前缀和、活动归并缓冲与递归栈。
关键点总结
[!green]
- 排序可以改变组内值位置，但左右组仍代表原始前后位置集合。
- 先统计再混合，避免丢失配对方向。
易错点总结
[!yellow]
- 上界用严格小于，会漏掉恰等于上界的和。
- 下界使用小于等于推进，会跳过恰等于下界的候选。
- 每个左值重置右指针，本层退化为平方扫描。
- 先全局排序或删除重复前缀值，会分别破坏下标先后关系或漏掉不同位置的区间。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 560. 和为 K 的子数组 | 中等 | 从前缀差恰为k扩展成位于闭区间，单值哈希查询需改为范围计数。 |
| 315. 计算右侧小于当前元素的个数 | 困难 | 同样可用归并或树状数组累计满足大小关系的历史元素数量。 |