Grizzly's daily
0%

数组解题技巧1——前缀和数组

发表于 更新于 分类于
本文字数： 2.3k 阅读时长 ≈ 2 分钟

本文是关于数组的前缀和技巧，在快速计算一个数组区间内的元素之和时使用

涉及 leetcode 的 303. 区域和检索 - 数组不可变、304. 二维区域和检索 - 矩阵不可变和560. 和为 K 的子数组。

区域检索

题目1

首先来看题目303. 区域和检索 - 数组不可变：给定一个整数数组 nums，求出数组从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点。

示例1：

输入：[ [ [-2, 0, 3, -5, 2, -1] ], [0, 2], [2, 5], [0, 5] ]

输出：[null, 1, -1, -3]

理解一下1

题目的大概意思就是：计算数组内某个区域的和。

代码要求有两点，一个是写出构造函数，一个是写出计算区域和的函数。

基本的思路是：

  1. 构造函数直接将数组传递过去就行；
  2. 在sumRange中使用循环计算left到right的和。

很简单的嘛，OK确实，但是提交了发现超越的人数不多呀，这怎么行！

仔细思考发现 OJ 测试的时候构造函数仅仅调用一次，而计算区域和函数调用了多次，所以我们需要优化sumRange函数。

于是考虑使用前缀和，使得构造函数麻烦一些，但是使得sumRange函数简单一些：

  1. 使用构造函数时，直接在传递数组时，计算前n项的前缀累加和，时间复杂度为O(n)；
  2. 然后sumRange函数计算left到right的区域和时，只需要使用第right项的前缀和减去第left-1项前缀和即可，sumRange的时间复杂度就是O(1)。

解题1

先看解法一：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class NumArray {
private:
    vector<int> nums;
public:
    NumArray(vector<int>& nums) {
        this->nums = nums;
    }
    
    int sumRange(int left, int right) {
        int sum = 0;
        for(int i = left; i <= right; i++){
            sum += this->nums[i];
        }
        return sum;
    }
};

再看使用前缀和的解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class NumArray {
private:
    vector<int> presums;
public:
    NumArray(vector<int>& nums) {
        // 构造时为 n 的复杂度
        int n = nums.size();
        this->presums.resize(n+1);
        for(int i = 1; i < n+1; i++){
            this->presums[i] = this->presums[i-1] + nums[i-1];
        }
    }
    // 调用时仅需要直接索引相减即可
    int sumRange(int left, int right) {
        return this->presums[right+1] - this->presums[left];
    }
};

关于304. 二维区域和检索 - 矩阵不可变这题，只不过是从一维变化成了二维，大家举一反三即可。

需要注意的仅仅是边界的细节问题。

和为 K 的子数组

题目2

首先来看题目560. 和为 K 的子数组：给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的连续子数组的个数。

示例1：

输入：nums = [1,1,1], k = 2

输出：2

示例2：

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

输出：2

理解一下2

题目的大概意思就是：计算出，给定数组中有多少个连续子数组的和为 K，也就是给定数组中有多少个区间和为K。

最基本的思路就是穷举嘛，嵌套循环，计算所有区间的数组之和，判断其是否为 K。不过很遗憾，时间复杂度\(O(n^2)\)在10000大小的测试案例中超时了。

再仔细看看区域和为K，关于区域和那我们很自然的想到使用前缀和数组试试看了：

  1. 计算前缀和数组；
  2. 我们要计算区域和，就得使用前缀和数组的端点值相减，并判断是否为K，如此一来时间复杂度又回到了\(O(n^2)\)；
  3. 换个思路，验证i处的前缀和sum_i减去K的差值sum_j，判断sum_j是否已经存在已知的前缀和数组中，若存在则统计出现次数即可！
  4. sum_j出现的次数就是i为右端点的区间可以出现的次数，随着不断计算前缀和数组和计数，那么时间复杂度仅仅是计算前缀和的时间O(n)。

题解2

判断存在计数可以使用hash表来实现，快速高效。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int subarraySum(vector<int>& nums, int k) {
    // 使用hash表来记录前缀和出现的次数
    unordered_map<int,int> presum;
    // 初始记录为 0，因为存在一个数等于 k 的情况
    presum[0] = 1;
    // count 记录个数，sum_i 计算前缀和
    int count = 0, sum_i = 0;
    for(int num: nums){
        sum_i += num;
        int sum_j = sum_i - k;
        // 相差为 k 的前缀和若存在，则区域相加为 k
        if(presum.find(sum_j) != presum.end()){
            // 加上此前出现 sum_j 的次数
            count += presum[sum_j];
        }
        presum[sum_i]++; // 出现次数加 1
    }
    return count;
}

个人收获

前缀和的计算方法主要适用于处理数组区域之和的问题，并且计算区域和频率较高时使用，能够达到较好的效果。

------ 本文结束------