数组篇：前缀和数组和差分数组

# 一、前缀和数组

# 303. 区域和检索 - 数组不可变 (opens new window)

☀️☀️☀️☀️☀️☀️题解一：一维前缀和数组

class NumArray {

    //前缀和
    int[] preSum;
    public NumArray(int[] nums) {
        int m = nums.length;
        preSum = new int[m+1];
        for(int i=0;i<m;i++){
            preSum[i+1] = preSum[i]+nums[i];
        }
    }
    
    public int sumRange(int left, int right) {
        return preSum[right+1] - preSum[left];
    }
}

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

# 剑指 Offer II 013. 二维子矩阵的和 (opens new window)

☀️☀️☀️☀️☀️☀️题解一：二维前缀和数组

class NumMatrix {
		//前缀和
    private int[][] preSum;

    public NumMatrix(int[][] matrix) {
        int m = matrix.length,n = matrix[0].length;
        preSum = new int[m+1][n+1];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                preSum[i+1][j+1] = preSum[i][j+1] + preSum[i+1][j] + matrix[i][j] - preSum[i][j];
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return preSum[row2+1][col2+1] - preSum[row2+1][col1] - preSum[row1][col2+1] + preSum[row1][col1];
    }
}

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

# 二、差分数组

差分数组工具类

//差分数组工具类
    class Difference {
        //差分数组
        private int[] diff;

        public Difference(int[] nums) {
            //初始化差分数组 diff[i] = nums[i] - nums[i - 1];
            diff = new int[nums.length];
            diff[0] = nums[0];
            for (int i = 1; i < nums.length; i++) {
                diff[i] = nums[i] - nums[i - 1];
            }
        }

        //给区间[i,j]增加val
        public void increment(int i, int j, int val) {
            diff[i] += val;
            if (j + 1 < diff.length) {
                diff[j + 1] -= val;
            }
        }

        //返回结果
        public int[] result() {
            int[] res = new int[diff.length];
            res[0] = diff[0];
            for (int i = 1; i < diff.length; i++) {
                res[i] = diff[i] + res[i - 1];
            }
            return res;
        }
    }

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
29
30
31
32

# 1094. 拼车 (opens new window)

☀️☀️☀️☀️☀️☀️题解一：

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        int[] nums = new int[1001];
        Difference difference = new Difference(nums);
        for (int[] trip : trips) {
            // 即乘客在车上的区间是 [trip[1], trip[2] - 1]
            difference.increment(trip[1], trip[2] - 1, trip[0]);
        }

        int[] res = difference.result();
        // 客车自始至终都不应该超载
        for (int i = 0; i < res.length; i++) {
            if(res[i] > capacity){
                return false;
            }
        }
        return true;
    }
}

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

# 1109. 航班预订统计 (opens new window)

☀️☀️☀️☀️☀️☀️题解一：

class Solution {
    public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] res = new int[n];
        Difference difference = new Difference(res);
        for(int[] tmp : bookings){
            difference.increment(tmp[0]-1,tmp[1]-1,tmp[2]);
        }
        return difference.result();
    }
}

1
2
3
4
5
6
7
8
9
10

← 数组篇：双指针技巧数据结构与算法--跳表→