秋招-算法-查分与前缀和数组篇

差分数组

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

1109. 航班预订统计

class Solution {
    public int[] corpFlightBookings(int[][] bookings, int n) {
         //构建差分数组，记录初始结束位置，开始为+，结束为减
        int[] memo = new int[n+2];
        for (int i = 0; i < bookings.length; i++) {
            memo[bookings[i][0]] += bookings[i][2];
            memo[bookings[i][1]+1] -= bookings[i][2];
        }
        //根据差分数组和前一个结果推出此轮结果
        int[] res = new int[n];
        res[0] = memo[1];
        for (int i = 1; i < res.length; i++) {
            res[i] = res[i-1] + memo[i+1];
        }
        
        return res;
    }
}

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

前缀和数组

前缀和技巧适用于快速、频繁地计算一个索引区间内的元素之和。

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

class NumArray {

    int[] memo ;
    public NumArray(int[] nums) {
        // preSum[0] = 0，便于计算累加和
        memo = new int[nums.length+1];
        memo[0] = 0;
        for (int i = 0; i < nums.length; i++) {

                memo[i+1] = memo[i+1-1]+nums[i];
        }
    }

    public int sumRange(int left, int right) {
        // if (left!=0)
            return memo[right+1] - memo[left];
        
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19