LC 327. 区间和的个数
题目描述
这是 LeetCode 上的 327. 区间和的个数 ，难度为 困难。
给你一个整数数组 nums 以及两个整数 lower 和 upper 。求数组中，值位于范围 $[lower, upper]$ （包含 lower 和 upper）之内的 区间和的个数 。
区间和 $S(i, j)$ 表示在 nums 中，位置从 $i$ 到 $j$ 的元素之和，包含 $i$ 和 $j$ (i ≤ j)。
示例 1：1
2
3
4
5输入：nums = [-2,5,-1], lower = -2, upper = 2
输出：3
解释：存在三个区间：[0,0]、[2,2] 和 [0,2] ，对应的区间和分别是：-2 、-1 、2 。
示例 2：1
2
3输入：nums = [0], lower = 0, upper = 0
输出：1
提示：
- $1 <= nums.length <= 10^5$
- $-2^{31} <= nums[i] <= 2^{31} - 1$
- $-10^5 <= lower <= upper <= 10^5$
- 题目数据保证答案是一个 $32$ 位 的整数
树状数组（离散化）
由于区间和的定义是子数组的元素和，容易想到「前缀和」来快速求解。
对于每个 $nums[i]$ 而言，我们需要统计以每个 $nums[i]$ 为右端点的合法子数组个数（合法子数组是指区间和值范围为 $[lower, upper]$ 的子数组）。
我们可以从前往后处理 $nums$，假设当前我们处理到位置 $k$，同时下标 $[0, k]$ 的前缀和为 $s$，那么以 $nums[k]$ 为右端点的合法子数组个数，等价于在下标 $[0, k - 1]$ 中前缀和范围在 $[s - upper, s - lower]$ 的数的个数。
我们需要使用一个数据结构来维护「遍历过程中的前缀和」，每遍历 $nums[i]$ 需要往数据结构加一个数，同时每次需要查询值在某个范围内的数的个数。涉及的操作包括「单点修改」和「区间查询」，容易想到使用树状数组进行求解。
但值域的范围是巨大的（同时还有负数域），我们可以利用 $nums$ 的长度为 $10^5$ 来做离散化。我们需要考虑用到的数组都有哪些：
- 首先前缀和数组中的每一位 $s$ 都需要被用到（添加到树状数组中）；
- 同时对于每一位 $nums[i]$（假设对应的前缀和为 $s$），我们都需要查询以其为右端点的合法子数组个数，即查询前缀和范围在 $[s - upper, s - lower]$ 的数的个数。
因此对于前缀和数组中的每一位 $s$，我们用到的数有 $s$、$s - upper$ 和 $s - lower$ 三个数字，共有 $1e5$ 个 $s$，即最多共有 $3 \times 10^5$ 个不同数字被使用，我们可以对所有用到的数组进行排序编号（离散化），从而将值域大小控制在 $3 \times 10^5$ 范围内。
代码：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
40class Solution {
int m;
int[] tr = new int[100010 * 3];
int lowbit(int x) {
return x & -x;
}
void add(int x, int v) {
for (int i = x; i <= m; i += lowbit(i)) tr[i] += v;
}
int query(int x) {
int ans = 0;
for (int i = x; i > 0; i -= lowbit(i)) ans += tr[i];
return ans;
}
public int countRangeSum(int[] nums, int lower, int upper) {
Set<Long> set = new HashSet<>();
long s = 0;
set.add(s);
for (int i : nums) {
s += i;
set.add(s);
set.add(s - lower);
set.add(s - upper);
}
List<Long> list = new ArrayList<>(set);
Collections.sort(list);
Map<Long, Integer> map = new HashMap<>();
for (long x : list) map.put(x, ++m);
s = 0;
int ans = 0;
add(map.get(s), 1);
for (int i : nums) {
s += i;
int a = map.get(s - lower), b = map.get(s - upper) - 1;
ans += query(a) - query(b);
add(map.get(s), 1);
}
return ans;
}
}
- 时间复杂度：去重离散化的复杂度为 $O(n\log{n})$；统计答案的复杂度为 $O(n\log{n})$
- 空间复杂度：$O(n)$
线段树（动态开点 + STL）
值域范围爆炸，但是数组长度（查询次数）有限，容易想到「线段树（动态开点）」。
但如果按照我们 729. 我的日程安排表 I、731. 我的日程安排表 II 和 732. 我的日程安排表 III 系列题解的求解方式「估点 + 静态数组 + 动态 new」，仍无法解决 MLE 问题。
究其原因，我们在 [日程安排表] 系列中使用到的方式存在「固定双边开点（一旦要对 $u$ 的子节点开点，会同时将左右子节点都开出来）」以及「查询时也会触发开点」的问题，导致我们最多处理值域范围在 $1e9$ 的情况。
对于本题的值域范围远超 $1e9$，我们需要考虑修「静态数组」和「开点方式」来解决 MLE 问题：
- 由于值域太大，采用估点方式来开精挑数组会直接导致
MLE，我们使用支持扩容的STL容器； 由于同时开点和查询也会触发开点，会导致我们不必要的空间浪费，我们直接将开点操作放在
update实现中，并且只有当需要查询到左子节点才对左子节点进行开点，当查询到右子节点才对右子节点进行开点。代码：
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
49
50
51
52class Solution {
class Node {
int ls = -1, rs = -1, val = 0;
}
List<Node> tr = new ArrayList<>();
void update(int u, long lc, long rc, long x, int v) {
Node node = tr.get(u);
node.val += v;
if (lc == rc) return ;
long mid = lc + rc >> 1;
if (x <= mid) {
if (node.ls == -1) {
tr.add(new Node());
node.ls = tr.size() - 1;
}
update(node.ls, lc, mid, x, v);
} else {
if (node.rs == -1) {
tr.add(new Node());
node.rs = tr.size() - 1;
}
update(node.rs, mid + 1, rc, x, v);
}
}
int query(int u, long lc, long rc, long l, long r) {
if (u == -1) return 0;
if (r < lc || l > rc) return 0;
Node node = tr.get(u);
if (l <= lc && rc <= r) return node.val;
long mid = lc + rc >> 1;
return query(node.ls, lc, mid, l, r) + query(node.rs, mid + 1, rc, l, r);
}
public int countRangeSum(int[] nums, int lower, int upper) {
long L = 0, R = 0, s = 0;
for (int i : nums) {
s += i;
L = Math.min(Math.min(L, s), Math.min(s - lower, s - upper));
R = Math.max(Math.max(R, s), Math.max(s - lower, s - upper));
}
s = 0;
int ans = 0;
tr.add(new Node());
update(0, L, R, 0, 1);
for (int i : nums) {
s += i;
long a = s - upper, b = s - lower;
ans += query(0, L, R, a, b);
update(0, L, R, s, 1);
}
return ans;
}
}
- 时间复杂度：令 $n$ 为数组长度，$m$ 为值域大小，复杂度为 $O(n\log{m})$
- 空间复杂度：$O(n\log{m})$
线段树（动态指针）
更进一步，我们可以连 STL 都不使用，直接在 Node 的定义时，将左右子节点的引用存放起来。
虽然这样不会带来空间上的优化，但可以有效避免 STL 的创建、访问和扩容（实际运行相比解法二，用时少一半）。
代码：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
44class Solution {
class Node {
Node ls, rs;
int val = 0;
}
void update(Node node, long lc, long rc, long x, int v) {
node.val += v;
if (lc == rc) return ;
long mid = lc + rc >> 1;
if (x <= mid) {
if (node.ls == null) node.ls = new Node();
update(node.ls, lc, mid, x, v);
} else {
if (node.rs == null) node.rs = new Node();
update(node.rs, mid + 1, rc, x, v);
}
}
int query(Node node, long lc, long rc, long l, long r) {
if (node == null) return 0;
if (r < lc || l > rc) return 0;
if (l <= lc && rc <= r) return node.val;
long mid = lc + rc >> 1;
return query(node.ls, lc, mid, l, r) + query(node.rs, mid + 1, rc, l, r);
}
public int countRangeSum(int[] nums, int lower, int upper) {
long L = 0, R = 0, s = 0;
for (int i : nums) {
s += i;
L = Math.min(Math.min(L, s), Math.min(s - lower, s - upper));
R = Math.max(Math.max(R, s), Math.max(s - lower, s - upper));
}
s = 0;
int ans = 0;
Node root = new Node();
update(root, L, R, 0, 1);
for (int i : nums) {
s += i;
long a = s - upper, b = s - lower;
ans += query(root, L, R, a, b);
update(root, L, R, s, 1);
}
return ans;
}
}
- 时间复杂度：令 $n$ 为数组长度，$m$ 为值域大小，复杂度为 $O(n\log{m})$
- 空间复杂度：$O(n\log{m})$
最后
这是我们「刷穿 LeetCode」系列文章的第 No.327 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！
