LeetCode高频算法解题套路-前缀和与差分数组

发表于 更新于 分类于 阅读次数：

1. 原理简介

1.1 前缀和（Prefix Sum）

定义：prefix[i] = nums[0] + nums[1] + ... + nums[i-1]

**用途：**快速求某一区间 [l, r] 的和：prefix[r+1] - prefix[l]

1.2 差分数组（Difference Array）

定义：diff[i] = nums[i] - nums[i-1]，逆运算为前缀和，对差分数组求前缀和，即可得到原数组。

**用途：**快速对区间 [l, r] 做加减操作，再还原原数组。当我们希望对原数组的某一个区间 [l,r] 施加一个增量inc 时，差分数组 d 对应的改变是：d[l] 增加 inc，d[r+1] 减少 inc。这样对于区间的修改就变为了对于两个位置的修改。并且这种修改是可以叠加的，即当我们多次对原数组的不同区间施加不同的增量，我们只要按规则修改差分数组即可。

2. 典型题目

2.1 前缀和

LeetCode - 303. 区域和检索 - 数组不可变

难度：简单

题目：给定一个整数数组 nums，处理以下类型的多个查询:

  1. 计算索引 left 和 right （包含 left 和 right）之间的 nums 元素的 和 ，其中 left <= right

实现 NumArray 类：

  • NumArray(int[] nums) 使用数组 nums 初始化对象
  • int sumRange(int i, int j) 返回数组 nums 中索引 left 和 right 之间的元素的 总和 ，包含 left 和 right 两点（也就是 nums[left] + nums[left + 1] + ... + nums[right] )

解题思路：

很简单的题目，求指定区间的和，完全符合前缀和适用场景。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class NumArray {

    private final int[] prefixSumArr;

    public NumArray(int[] nums) {
        int size = nums.length;
        prefixSumArr = new int[size];
        int sum = 0;
        for (int i = 0; i < size; i++) {
            sum += nums[i];
            prefixSumArr[i] = sum;
        }
    }
    
    public int sumRange(int left, int right) {
        return prefixSumArr[right] - (left == 0 ? 0 : prefixSumArr[left - 1]);	// 前面多加一个0更好
    }
}

复杂度分析：

时间复杂度：O(n), sumRange方法O(1)

空间复杂度：O(n)

LeetCode - 724. 寻找数组的中心下标

难度：简单

题目：给你一个整数数组 nums ，请计算数组的 中心下标 。

数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。

如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。

如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。

解题思路：

  1. 第1次遍历，预计算前缀和，并对左右两侧分别扩充1个0
  2. 第2次遍历，找到下标 i 满足 psa[i-1] == psa[len+1] - psa[i]，否则返回 -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int pivotIndex(int[] nums) {

        int len = nums.length;
        int[] psa = new int[len + 2];
        psa[0] = 0;
        psa[len + 1] = 0;
        
        int sum = 0;
        for (int i = 0; i < len; i++) {
            sum += nums[i];
            psa[i + 1] = sum;
        }

        for (int i = 1; i < len + 1; i++) {
            if (psa[i - 1] == (psa[len] - psa[i])) {
                return i - 1;
            }
        }
        return -1;
    }
}

复杂度分析：

时间复杂度：O(n)

空间复杂度：O(n)

LeetCode - 560. 和为 K 的子数组

《 LeetCode高频算法解题套路-哈希表》

2.2 差分数组

LeetCode - 1109. 航班预订统计

难度：中等

题目：这里有 n 个航班，它们分别从 1 到 n 进行编号。

有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。

请你返回一个长度为 n 的数组 answer，里面的元素是每个航班预定的座位总数。

解题思路：

  1. 将所有指定区间[first, last]的增量seats累计到一个差分数组。（累计方法：diff[first] += seats; diff[last+1] -= seats;，注：last+1需判定数组下标越界)
  2. 对diff数组求前缀和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int[] corpFlightBookings(int[][] bookings, int n) {
        
        // 本质就是在nums的指定区间[first, last]增加seats, 然后用前缀和还原
        int[] nums = new int[n];
        for (int[] booking : bookings) {
            nums[booking[0] - 1] += booking[2];
            if (booking[1] < n) {
                nums[booking[1]] -= booking[2];
            }
            // System.out.println(Arrays.toString(nums));
        }

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

        return nums;
    }
}

复杂度分析：

时间复杂度：O(n)

空间复杂度：O(n)

LeetCode - 1094. 拼车

难度：中等

题目：车上最初有 capacity 个空座位。车 只能 向一个方向行驶（也就是说，不允许掉头或改变方向）

给定整数 capacity 和一个数组 trips , trip[i] = [numPassengersi, fromi, toi] 表示第 i 次旅行有 numPassengersi 乘客，接他们和放他们的位置分别是 fromi 和 toi 。这些位置是从汽车的初始位置向东的公里数。

当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false。

解题思路：

和 1109.航班预订统计 一样

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
class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        // 和航班类似
        int toMax = 0;
        for (int[] trip : trips) {
            toMax = Math.max(toMax, trip[2]);
        }
        
        int[] diff = new int[toMax];

        for (int[] trip : trips) {
            diff[trip[1]] += trip[0];
            if (trip[2] < toMax) {
                diff[trip[2]] -= trip[0];
            } 
        }

        // 本质还是求前缀和，检查是否存在 > capacity 的元素
        int count = 0;
        for (int i = 0; i < toMax; i++) {
            count += diff[i];
            if (capacity < count) {
                return false;
            }
        }
        return true;
    }
}

复杂度分析：

时间复杂度：O(n)

空间复杂度：O(n)