前缀和与差分

发表于 | 分类于 | |
字数统计: 1,218 | 阅读时长 ≈ 5

引言

前缀和与差分，这两个算法的本质思想是一致的，很简单，但是在某些场景下，应用这两种算法还是会起到奇效的，下面我们就来分析下这两种算法

前缀和

以数组举例，前缀和就是指，当前索引位置存放的数据是前面所有数据的和，如下图所示：

这么做有什么用的？实际上就是在某些场景下，能够减少重复计算。

我们通过leetcode的几个题目来分析

区域和检索 - 数组不可变

这道题目很简单，要求计算一定区间范围内的数据的和。那么实际上就可以计算出前缀和，然后用减法解决（这有些动态规划的味道）

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

    vector<int> sumNum;
};

一般这种区间范围的和的问题，大多都可以用前缀和的思想来解决

上面的这个题目有些太简单了，实际上，前缀和很多时候是作为解决方案的初级处理，下面我们来看一个没有那么直白明显的问题

连续的子数组和

差分

前缀和是讲前面的数据累加起来，而差分则是将相邻的数据相减，如下图所示：

这有什么用呢？看上去没什么用。实际上差分的应用场景是：

差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减。

假设我们有数组【8， 2， 6， 3， 1】，我们首先要对nums[1:4] + 3，然后对nums[2:4] - 5, 然后对 nums[3:4] + 8 等等后续的1000个操作。

那么我们怎么处理？一种朴素的方法是用两层for循环，一个条件一个条件的计算，但是这样会有一个后果，那就是太慢了，部分索引需要重复累加。那有没有更好的方法呢？差分就能解决这个问题

差分数组的构造：
diff[0] = nums[0];
diff[i] = nums[i] - nums[i-1];

根据差分数组可以恢复原数组：
res[0] = diff[0];
res[i] = res[i - 1] + diff[i];

插一句：把差分做前缀和就是原数组

因此我们将diff[i] + 3, 当还原成元数组的时候，就相当于nums是[i:] + 3
将diff[j] - 3，就相当于nums[0:j] - 3

因此nums[1:4] + 3反应到diff里面就是

diff[1] + 3

diff[4] - 3

这里原来4步的运算精简为了2步。如果原来的是nums[1:40000] + 3就相当于把40000步的运算精简为了2步。这就是查分的价值。

讲所有的频繁加减运算完毕后，只需要做一步还原就可以得到原始数组额计算结果了。

下面我们以几个例题来分析实践一下

航班预订统计

这个题目如果以朴素的算法计算的话，必然的结果就是超时，两层for循环，大量的重复循环操作。

1
2
3
4
5
6
7
8
9
10
11
int* corpFlightBookings(int** bookings, int bookingsSize, int* bookingsColSize, int n, int* returnSize){
    int* result = (int*)calloc(n + 1, sizeof(int));
    *returnSize = n;
    for (int i = 0; i < bookingsSize; i++) {
        for (int j = bookings[i][0]; j <= bookings[i][1]; j++) {
            result[j - 1] += bookings[i][2];
        }
    }

    return result;
}

上面介绍了差分可以精简区间范围内的重复计算，下面用查分来解决这个问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> diff(n);
        for (auto booking : bookings) {
            diff[booking[0] - 1] += booking[2];
            if (booking[1] < n) {
                diff[booking[1]] -= booking[2];
            }
        }

        for (int i = 1; i < n; ++i) {
            diff[i] += diff[i-1];
        }
        return diff;
    }
};

这个题目需要注意的点有如下两点

  • 题目中是闭区间
  • 边界要处理好

拼车

跟上面的题目是一个类型的，解决方案也是一致的，基本代码都是一个套路。

但是需要注意：

  • 要提前判断是不是if (trip[0] > capacity) ，这种场景下直接返回false，因此在最起始的时候就是做不了车的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        vector<int> diff(1001);
        if (trips[0][0] > capacity) {
            return false;
        }
        for (auto trip : trips) {
            diff[trip[2]] -= trip[0];
            diff[trip[1]] += trip[0];
        }

        for (int i = 1; i < 1001; ++i) {
            diff[i] += diff[i-1];
            if (diff[i] > capacity) {
                return false;
            }
        }
        return true;
    }
};

总结

  • 前缀和在某些场景下会节省计算量，有些动态规划的思想
  • 差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减
显示 Gitment 评论