算法数据结构

在数据结构中维护前缀和：区间(矩形/路径)和等于(大于)目标值

字数统计: 1.8k字   |   阅读时长: 7分
,

摘要: 区间和等于目标值的各种变种问题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章 【模板】前缀和与差分 中我们了解了一维和二维前缀和的算法原理和代码模板。在实际问题中我们经常要将前缀和维护在数据结构中，以便于后续的多次查询。在 前缀和问题分类汇总 中给出了一些题目清单可以参考。

本文我们处理一类用数据结构维护前缀和解决的问题，基础版本为[是否存在/存在多少]区间和为 target。将数组改为矩阵和树，得到二维版本和树形版本的问题。以及将“等于”改为“大于”，又可以得到一个变种问题，本文分别解决这些问题，有的问题此前解决过，将给出文章链接，总结如下：

问题 题目链接 维护前缀和的数据结构
是否存在区间和为 target - 哈希集合
有多少区间和为 target 560. 和为K的子数组 哈希映射
有多少矩阵和为 target 1074. 元素和为目标值的子矩阵数量 哈希映射
有多少路径和为 target 437. 路径总和 III 哈希映射
有多少区间和大于 target 327. 区间和的个数 线段树/树状数组

经典一问：是否存在区间和为 target

给定数组 $a_{0}, a_{1}, …, a_{n-1}$，问 $a$ 上有没有一个区间，其和为 target。

算法：前缀和 + 哈希集合

对于这经典一问，思路如下：

当扫描到 i 时， $a_{0}, a_{1}, …, a_{i-1}$ 的前缀和都已经求过了，把它们维护到 unordered_set 中，求完当前值 a[i] 对应的前缀和 S[i+1], 在插入到 unordered_set 之前先问：S[i+1] - target 在 unordered_set 中是否出现，如果出现则找到答案。

基础问题：有多少区间的和为 target

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

提示：

1
2
3
1 <= nums.length <= 2e4
-1000 <= nums[i] <= 1000
-1e7 <= k <= 1e7

示例 1：
输入：nums = [1,1,1], k = 2
输出：2

示例 2：
输入：nums = [1,2,3], k = 3
输出：2

算法：前缀和 + 哈希表

在经典一问的基础上，把问是否存在该为问存在多少个，则得到当前的变种问题。

整体思路与经典一问一模一样。仅把 unordered_set 改成 unordered_map 就可以。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        // 把所有前缀和保存到 unordered_map 中
        // 一遍 init 前缀和数组一遍把前缀和存入 map
        // 遍历的新的前缀和 S[i] 的时候，看有 map 没有元素为 S[i] - target
        if(nums.empty()) return 0;
        int n = nums.size();
        vector<int> sums(n + 1, 0); // sums[0] = 0 是第一个前缀和
        unordered_multiset<int> sum_count;
        sum_count.insert(0); // 0 要初始化进去
        int result = 0;
        for(int i = 1; i < n + 1; ++i)
        {
            sums[i] = nums[i - 1] + sums[i - 1];
            result += sum_count.count(sums[i] - k);
            sum_count.insert(sums[i]);
        }
        return result;
    }
};

树形版本：有多少路径的和为 target

基本问题是问数组上有多少个区间的和为 target。

将数组改为树，问有多少路径的和为 target，即为基本问题的树形版本，也就是题目 437. 路径总和 III。

算法：DFS + 前缀和 + 哈希映射

dfs(前序遍历)时，栈里存的是当前节点到根的链，这条链上的和可以作为前缀和维护在 unordered_map 里。在维护的时候需要注意从左子树跳到右子树的时候，左子树的所有节点对应的前缀和要先从 unordered_map 中删掉。

参考文章 力扣437-路径总和3。

二维版本：有多少矩形的和为 target

基本问题是问数组上有多少个区间的和为 target。

将数组改为矩阵，问有多少矩形的和为 target，即为基本问题的二维版本，也就是题目 1074. 元素和为目标值的子矩阵数量。

算法：前缀和 + 哈希映射

参考文章 力扣1074-元素和为目标值的子矩阵数量。

有多少区间和大于 target

给你一个整数数组 nums 以及两个整数 lower 和 upper 。求数组中，值位于范围 [lower, upper] （包含 lower 和 upper）之内的 区间和的个数 。

区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。

示例 1：
输入：nums = [-2,5,-1], lower = -2, upper = 2
输出：3
解释：存在三个区间：[0,0]、[2,2] 和 [0,2] ，对应的区间和分别是：-2 、-1 、2 。

示例 2：
输入：nums = [0], lower = 0, upper = 0
输出：1

提示：

1
2
3
4
1 <= nums.length <= 1e5
-2^31 <= nums[i] <= 2^31 - 1
-1e5 <= lower <= upper <= 1e5
题目数据保证答案是一个 32 位 的整数

算法：前缀和 + 权值树状数组

基本问题是问数组上有多少个区间的和为 target。

把问题改为问有多少个区间的和大于/小于 target，记为当前的变种问题。

整体思路与经典一问基本一样，只是把 unordered_set 改成权值线段树/权值树状数组，树上保存前缀和及其对应的计数值。

对于一个前缀和的值 sums[i]，我们要找的是 target - sums[i]，因此权值线段树/树状数组的横坐标是所有的 target - sums[i]，纵坐标是计数。

代码 (C++)

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
class BIT {
public:
    BIT():sums(1, 0){}
    BIT(int n):sums(n + 1, 0){}

    void update(int index, int delta)
    {
        int n = sums.size();
        while(index < n)
        {
            sums[index] += delta;
            index += _lowbit(index);
        }
    }

    int query(int i)
    {
        int sum = 0;
        while(i > 0)
        {
            sum += sums[i];
            i -= _lowbit(i);
        }
        return sum;
    }

private:
    vector<int> sums;

    int _lowbit(int x)
    {
        return x & (-x);
    }
};

class Solution {
public:
    int countRangeSum(vector<int>& nums, int lower, int upper) {
        if(nums.empty()) return 0;
        int n = nums.size();

        // 前缀和
        vector<ll> sums(n + 1, 0);
        for(int i = 1; i <= n; ++i)
            sums[i] = sums[i - 1] + nums[i - 1];

        // 离散化
        vector<ll> x(sums.begin(), sums.end());
        for(ll sum: sums)
        {
            x.push_back(sum - (ll)lower);
            x.push_back(sum - (ll)upper);
        }
        sort(x.begin(), x.end());
        x.erase(unique(x.begin(), x.end()), x.end());

        int m = x.size();
        BIT bit(m);
        int result = 0;
        bit.update(_find(0, x), 1);
        for(int i = 0; i < n; ++i)
        {
            ll cur = sums[i + 1];
            result += bit.query(_find(cur - (ll)lower, x)) - bit.query(_find(cur - (ll)upper, x) - 1);
            bit.update(_find(cur, x), 1);
        }
        return result;
    }

private:
    using ll = long long;
    int _find(ll v, const vector<ll>& x)
    {
        return lower_bound(x.begin(), x.end(), v) - x.begin() + 1;
    }
};
Share