Grizzly's daily
0%

数组解题技巧2——差分数组

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

本文是关于数组的差分数组技巧，在对元素数组区间进行加减计算时使用。

涉及 leetcode 的370. 区间加法、1109. 航班预订统计和1094. 拼车。

合并两个有序链表

题目1

首先来看题目370. 区间加法：假设你有一个长度为 n 的数组，初始情况下所有的数字均为 0，你将会被给出 k 个更新的操作。其中，每个操作会被表示为一个三元组：[startIndex, endIndex, inc]，你需要将子数组 A[startIndex ... endIndex]（包括 startIndex 和 endIndex）增加 inc。

请你返回 k 次操作后的数组。

示例1：

输入：length = 5, updates = [ [1,3,2],[2,4,3],[0,2,-2] ]

输出：[-2,0,3,5,3]

理解一下1

题目的大概意思就是：

  1. 初始数组为元素均为 0；
  2. 三元组表示在区间startIndex到endIndex内的元素都加上inc。

最直白的思路就是，将每个三元组表示的区间一个一个加上值，很快就能实现，但是复杂度太高会超时，那么怎么办呢？

这里引入差分数组的概念：

差分数组就是在原长度为n的nums数组上，构建一个长度为n+1的数组diff，diff[i] = nums[i] - nums[i-1]，也就是原数组相邻两项的之差。

当差分数组计算完成之后再通过nums[i] = nums[i-1] + diff[i]即可还原得到相应的数组。

对差分数组的第i项进行计算，都会同等影响到之后的剩余项，这就是差分数组的性质！

因此，我们可以在差分数组上对第first项加上seats，使得后续的每一项都会增加seats，但是我们只想增加到第last项，所以在第last+1项之后再减去seats，就可以抵消该影响啦！

ok，那我们就来看代码吧！

解题1

构建差分数组的时候，使得差分数组的长度为n+1可以使得不用判断数组越界的问题，这个和链表增加头结点有异曲同工之妙。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {
    // 实际上计算的nums是差分数组，只不过这里开始都为0
    vector<int> nums(length+1, 0);
    for(int i = 0; i < updates.size(); i++){
        nums[updates[i][0]] += updates[i][2];
        nums[updates[i][1]+1] -= updates[i][2];
    }
    // 差分数组还原
    for(int i = 1; i < length; i++){
        nums[i] += nums[i-1];
    }
    nums.pop_back();
    return nums;
}

关于1109. 航班预订统计和1094. 拼车这两个问题实际上就是将该简单问题应用到实际场景中了，学会了这个差分数组的思想就很容易了，只需要注意端点细节处理即可。

个人收获

  1. 前缀和数组用于计算区域和问题，差分数组用于区域元素同时加减问题，而且使用频率较高时使用效果较好。

  2. 注意将数组长度扩大一个，这个在计算相邻项的时候就无需判断在数组最后是否会出现数组越界的问题，与链表中增加头结点的效果类似。

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