5.力扣327区间和的个数
https://leetcode.cn/problems/count-of-range-sum/description/
- 这道题最暴利的解法就是\(O(n^3)\)
- 第一层循环 (i): 遍历数组，以确定区间的起始位置
i。i从0遍历到n-1。 - 第二层循环 (j): 遍历数组，以确定区间的结束位置
j。j从i遍历到n-1。这样[i, j]就形成了一个有效的区间。 - 第三层循环 (k): 计算区间
[i, j]的和。k从i遍历到j，将nums[k]累加起来。 - 判断: 每次计算出区间和
sum后，检查sum是否满足lower <= sum <= upper。如果满足，就将计数器加一。
【下面介绍其他解法，用归并排序完成】。
首先，第一个前置知识就是累加和的数组。参考力扣有道题就是设计这个累加和数组数据结构的（力扣1480）：https://leetcode.cn/problems/running-sum-of-1d-array/description/
前置-前缀和-力扣1480累加和数组
题解：
1
2
3
4
5
6
7
8
class Solution {
public int[] runningSum(int[] nums) {
for (int i = 1; i < nums.length ;i++) {
nums[i] = nums[i - 1] + nums[i];
}
return nums;
}
}
有了这个累加和的数组，就可以把前面的暴力解法优化为\(O(n^2)\)
归并排序可以把这道题优化到\(O(NlogN)\)的时间复杂度。
归并排序解法
求必须以下标i位置结尾的子数组，
目标有多少个在[low,up]的范围上，
等同于去求，
i之前的所有前缀和中有多少个前缀和在[x-up, x- low]上
所以使用归并排序的改写，对前缀和数组进行归并改写，求出范围
在前缀和数组左右两组合并之前，右组中的每一个数表示的前缀和，都是在左组中任何一个数表示的前缀和的右边的，其实只要保证这个顺序就可以，至于左组内的数是什么顺序，对于【计算右组中一个数x，左组中有几个数在[x-U,x-L]上】这件事情来说，没有影响，只是当左组有序的时候，计算起来能达到指针不回退，效率更高。
当左右两组合并在一起的时候，这时候合并后的这个大组，会继续作为某一个左组，去和另一个右组合并，
计算结果都是在合并之前进行的，所以是对的
合并以后组内不会进行任何比较，因为组内顺序已经被打乱，再次比较就没有意义。
下面解法尤其注意sum数组（前缀和）的类型最好是long,因为力扣测试用例中会有Integer最小值这种数出现，求和（两个最小值求和）会越界。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
long[] help;
public int countRangeSum(int[] nums, int lower, int upper) {
int N = nums.length;
long[] sum = new long[N];
help = new long[N];
sum[0] = nums[0];
for (int i = 1;i< N;i++) {
sum[i] = sum[i - 1] + (long)nums[i];
}
return count(sum, 0, N - 1, lower, upper);
}
public int count(long[] sum, int L, int R, int lower, int upper) {
if (L == R) {
return sum[L] >= lower && sum[L] <= upper ? 1 : 0;
}
int M = L + ((R - L) >> 1);
return count(sum, L, M, lower, upper) + count(sum, M + 1, R, lower, upper) + merge(sum, L, M, R, lower, upper);
}
public int merge(long[] sum, int L, int M, int R, int lower, int upper ) {
int ans = 0;
int windowL = L;
int windowR = L;
for (int i = M +1;i <= R;i++) {
long min = sum[i] - upper;
long max = sum[i] - lower;
while (windowR <= M && sum[windowR] <= max) windowR++;
while (windowL <= M && sum[windowL] < min) windowL++;
ans += (windowR - windowL);
}
int a = L, b = M + 1, i = L;
while (a <= M && b <= R) {
help[i++] = sum[a] <= sum[b] ? sum[a++] : sum[b++];
}
while (a <= M) {
help[i++] = sum[a++];
}
while (b <= R) {
help[i++] = sum[b++];
}
for (int j = L;j <= R;j++) {
sum[j] = help[j];
}
return ans;
}
}
