很楠不爱3

这个屌丝很懒，什么也没留下！

热门标签

力扣方法总结：前缀和、树状数组、差分数组_力扣树上差分

作者：很楠不爱3 | 2024-02-15 21:34:23

踩

力扣树上差分

303. 区域和检索 - 数组不可变 Medium 前缀和 2023/1/28

给定一个整数数组 nums，处理以下类型的多个查询:
计算索引 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] )

简而言之就是需要重复求多次数组中间一个区间[left, right]的和，用前缀和较为方便。

class NumArray {
public:
    // 前缀和数组
    vector<int> preSum; 
    NumArray(vector<int>& nums) {
        // 预先计算n+1个前缀和，分别为0,a0,a0+a1,...,a0+...+an-1
        preSum.resize(nums.size() + 1, 0);
        preSum[0] = 0;
        for (int i = 0; i < nums.size(); i++) {
            preSum[i + 1] = preSum[i] + nums[i];
        }
    }
    
    int sumRange(int left, int right) {
        // 如果前缀和数组长度为n则这里为preSum[right]-preSum[left - 1]
        // 但是left = 0时会越界！因此前缀和长度定为n+1
        return preSum[right + 1] - preSum[left];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

需要注意的技巧是这里前缀和数组的长度为n+1，分别为0,a0,a0+a1,…,a0+…+an-1，避免了left=0下标越界需要讨论的情况。

304. 二维区域和检索 - 矩阵不可变 Easy 前缀和 2023/1/28

给定一个二维矩阵 matrix，以下类型的多个请求：
计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。
实现 NumMatrix 类：
NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
int sumRegion(int row1, int col1, int row2, int col2) 返回左上角 (row1, col1) 、右下角 (row2, col2) 所描述的子矩阵的元素总和。

在这里插入图片描述

class NumMatrix {
public:
    // 二维前缀和数组(col+1*row+1)，其中preSum2D[i][j]表示matrix[i-1][j-1]上方所有元素和
    vector<vector<int>> preSum2D;

    NumMatrix(vector<vector<int>> &matrix) {
        int col = matrix.size();
        int row = matrix[0].size();
        // 前缀和数组大小比原数组多一行一列，便于初始化且避免下标越界
        preSum2D.resize(col + 1, vector<int>(row + 1, 0));
        // 构建二维数组，前缀和为 上方块前缀和+左方块前缀和-左上方块前缀和+本身
        for (int i = 1; i < col + 1; i++)
            for (int j = 1; j < row + 1; j++)
                preSum2D[i][j] =
                        matrix[i - 1][j - 1] + preSum2D[i - 1][j] + preSum2D[i][j - 1] - preSum2D[i - 1][j - 1];
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        // 元素总和为四部分前缀和加减，详见图
        return preSum2D[row2 + 1][col2 + 1] - preSum2D[row1][col2 + 1] - preSum2D[row2 + 1][col1] +
               preSum2D[row1][col1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

元素总和为四部分前缀和加减
在这里插入图片描述

需要注意的技巧是这里前缀和数组的大小比也原数组多一行一列，便于初始化且避免下标越界。

307. 区域和检索 - 数组可修改 Medium 树状数组 2023/1/29

给你一个数组 nums ，请你完成两类查询。
其中一类查询要求更新数组 nums 下标对应的值
另一类查询要求返回数组 nums 中索引 left 和索引 right 之间（包含）的nums元素的和，其中 left <= right
实现 NumArray 类：
NumArray(int[] nums) 用整数数组 nums 初始化对象
void update(int index, int val) 将 nums[index] 的值更新为 val
int sumRange(int left, int right) 返回数组 nums 中索引 left 和索引 right 之间（包含）的nums元素的和（即，nums[left] + nums[left + 1], …, nums[right]）

简而言之就是需要重复求多次数组中间一个区间[left, right]的和，且需要经常更新某个元素的值，此时再使用前缀和在更新时需要更新所有后面元素的值，时间复杂度为O(n²)，改用树状数组 简介详解可将时间复杂度降到O(logn)。

class NumArray {
public:
    vector<int> C; // 树状数组
    vector<int> nums;
    int n; // 数组总长度
    // 获取数x最低为为0的个数2^k
    int lowbit(int x) {
        return x & -x;
    }
    // 求和函数，累加所有前驱
    int getSum(int x) {
        int ans = 0;
        for (int i = x; i > 0; i -= lowbit(i)) ans += C[i];
        return ans;
    }
    // 修改函数，改动从叶子结点到根节点所有C[i]
    void modify(int x, int u) {
        for (int i = x; i < C.size(); i += lowbit(i)) C[i] += u;
    }

    NumArray(vector<int>& nums) : nums(nums){
        n = nums.size();
        C.resize(n + 1, 0);
        // 初始化
        for (int i = 0; i < n; i++) modify(i + 1, nums[i]);
    }
    
    void update(int index, int val) {
        // 修改为差值
        modify(index + 1, val - nums[index]);
        nums[index] = val; // 更新原数组
    }
    
    int sumRange(int left, int right) {
        return getSum(right + 1) - getSum(left);
    }
};
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
33
34
35
36
37

树状数组较难理解，以下是代码模板

	vector<int> C; // 树状数组
    // 获取数x最低为为0的个数2^k
    int lowbit(int x) {
        return x & -x;
    }
    // 求和函数，累加所有前驱
    int getSum(int x) {
        int ans = 0;
        for (int i = x; i > 0; i -= lowbit(i)) ans += C[i];
        return ans;
    }
    // 修改函数，改动从叶子结点到根节点所有C[i]
    void modify(int x, int u) {
        for (int i = x; i < C.size(); i += lowbit(i)) C[i] += u;
    }

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

724. 寻找数组的中心下标 Easy 前缀和 2023/1/30

给你一个整数数组 nums ，请计算数组的中心下标。
数组中心下标是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。
如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
如果数组有多个中心下标，应该返回最靠近左边的那一个。如果数组不存在中心下标，返回 -1 。
示例：
输入：nums = [1, 7, 3, 6, 5, 6]
输出：3
解释：
中心下标是 3 。
左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，
右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者相等。

先求前缀和，再遍历对于每个数，查找其在前缀和中对应的前一个元素和，判断其两倍是否等于综合减去当前元素值。

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        vector<int> preSum(nums.size() + 1, 0);
        // 计算前缀和数组
        for (int i = 0; i < nums.size(); i++)
            preSum[i + 1] = nums[i] + preSum[i];
        int allSum = preSum.back();
        for (int i = 0; i < nums.size(); i++) {
            // 对于每个数，查找其在前缀和中对应的前一个元素和，判断其两倍是否等于综合减去当前元素值
            if (2 * preSum[i] == allSum - nums[i])
                return i;
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

更巧妙的前缀和解法，边遍历边求和，更加清晰。

class Solution {
public:
    int pivotIndex(vector<int> &nums) {
        // 计算元素和
        int total = accumulate(nums.begin(), nums.end(), 0);
        int sum = 0;
        for (int i = 0; i < nums.size(); ++i) {
            // 判断左侧前缀和的两倍是否等于总和-当前元素和
            if (2 * sum == total - nums[i]) {
                return i;
            }
            // 边遍历边求和
            sum += nums[i];
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

需要注意的技巧是这里前缀和数组的长度为n+1，分别为0,a0,a0+a1,…,a0+…+an-1，避免了left=0下标越界需要讨论的情况。

238. 除自身以外数组的乘积 Medium 前缀积 2023/1/30

给你一个整数数组 nums，返回数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
题目数据保证数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位整数范围内。
请不要使用除法，且在 O(n) 时间复杂度内完成此题。
示例：
输入: nums = [1,2,3,4]
输出: [24,12,8,6]

本题的小难点在于不能使用除法，否则一个累乘除以各个元素就直接得到答案了。
考虑使用前缀积和后缀积，即从前遍历一遍计算每个元素前面所有元素的积(不包含其本身)，再从后面遍历一遍计算每个元素后面所有元素的积(不包含其本身)，最后相乘即可。
本解法的空间复杂度为O(n)，如要优化空间复杂度参考官网题解。

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        // 计算前缀积和后缀积(不包含元素本身)
        vector<int> preMul(nums.size(), 1);
        vector<int> postMul(nums.size(), 1);
        for (int i = 1; i < nums.size(); i++) {
            preMul[i] = preMul[i - 1] * nums[i - 1];
        }
        for (int j = nums.size() - 2; j >= 0; j--) {
            postMul[j] = postMul[j + 1] * nums[j + 1];
        }
        // 前缀和*后缀和即为答案
        vector<int> res(nums.size(), 1);
        for (int i = 0; i < nums.size(); i++)
            res[i] = preMul[i] * postMul[i];
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

560. 和为 K 的子数组 Medium 前缀和无序map 2023/1/31

给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的连续子数组的个数。
示例：
输入：nums = [1,1,1], k = 2
输出：2

先计算器前缀和，再使用unordered_map逐一将元素放入，并确定当前元素可构成连续子数组的个数。

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        // 计算前缀和
        vector<int> preSum(nums.size() + 1, 0);
        for (int i = 0; i < nums.size(); i++)
            preSum[i + 1] = preSum[i] + nums[i];
        unordered_map<int, int> m;
        int count = 0;
        // 使用unordered_map逐一将元素放入，并确定当前元素可构成连续子数组的个数
        for (int sum : preSum) {
            if (m.find(sum - k) != m.end()) {
                count += m[sum - k];
            }
            m[sum]++;
        }
        return count;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

525. 连续数组 Medium 前缀和无序map 2023/1/31

给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。
示例：
输入: nums = [0,1]
输出: 2
说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。

本题要求时间复杂度为O(n)，用到了非常巧妙的换数技巧：将原数组中的0替换成-1。这样计算前缀和后两个前缀和相等则说明找到了这样一个连续子数组。
计算完前缀和后，使用unordered_map记录前缀和容器及其最早出现的下标，如果有相同的前缀和，其下标差即为数组长度，如果没有则添加进map。

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        // 把数组中0替换成-1
        for (int i = 0; i < nums.size(); i++)
            if (nums[i] == 0)
                nums[i] = -1;
        // 计算前缀和
        vector<int> preSum(nums.size() + 1, 0);
        for (int i = 0; i < nums.size(); i++)
            preSum[i + 1] = preSum[i] + nums[i];
        // 使用unordered_map记录出现的前缀和及其最早出现的下标
        unordered_map<int, int> m;
        int maxlen = 0;
        for (int i = 0; i < preSum.size(); i++) {
            if (m.find(preSum[i]) != m.end()) {
                maxlen = max(maxlen, i - m[preSum[i]]);
            }
            else m[preSum[i]] = i;
        }
        return maxlen;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

上文介绍的前缀和等方法计算一段区间的数组和较为方便，但对于一个数组需要将某一段区间集体增加值/减少值时，使用差分数组会较为方便。讲解

1109. 航班预订统计 Medium 差分数组 2023/1/31

这里有 n 个航班，它们分别从 1 到 n 进行编号。
有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的每个航班上预订了 seatsi 个座位。
请你返回一个长度为 n 的数组 answer，里面的元素是每个航班预定的座位总数。
本题要求时间复杂度为O(n)，用到了非常巧妙的换数技巧：将原数组中的0替换成-1。这样计算前缀和后两个前缀和相等则说明找到了这样一个连续子数组。
示例：
输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
输出：[10,55,45,25,25]
解释：
航班编号 1 2 3 4 5
预订记录 1 ： 10 10
预订记录 2 ： 20 20
预订记录 3 ： 25 25 25 25
总座位数： 10 55 45 25 25
因此，answer = [10,55,45,25,25]

具体的思路是抽象差分数组数学模型->建立差分数组->还原原数组。
本题要注意的是建立差分数组时下标的问题。

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        // 建立差分数组
        vector<int> diff;
        diff.resize(n, 0);
        for (int i = 0; i < bookings.size(); i++){
            int first = bookings[i][0];
            int last = bookings[i][1];
            int val = bookings[i][2];
            diff[first - 1] += val;
            if (last != n)
                diff[last] -= val;
        }
        // 还原原数组
        vector<int> res;
        res.resize(n);
        res[0] = diff[0];
        for (int i = 1; i < diff.size(); i++)
            res[i] = res[i - 1] + diff[i];
        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

1094. 拼车 Medium 差分数组 2023/1/31

车上最初有 capacity 个空座位。车只能向一个方向行驶（也就是说，不允许掉头或改变方向）
给定整数 capacity 和一个数组 trips , trip[i] = [numPassengersi, fromi, toi] 表示第 i 次旅行有 numPassengersi 乘客，接他们和放他们的位置分别是 fromi 和 toi 。这些位置是从汽车的初始位置向东的公里数。
当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false。
示例：
输入：trips = [[2,1,5],[3,3,7]], capacity = 4
输出：false

本题的难点在于抽象差分数组数学模型，使用差分数组建立各站台车上人数数组，由题干toi<=1000设为1001个站台，建立完差分数组后在还原的同时判断是否有车上人数>capacity的情形。要注意边界情况nums[0]的讨论。

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        // 构建查分数组，由于to最大值为1000，定义1001个车站
        vector<int> diff_nums(1001, 0);
        for (auto trip : trips) {
            int num = trip[0];
            int from = trip[1];
            int to = trip[2];
            diff_nums[from] += num;
            diff_nums[to] -= num;
        }
        // 还原数组
        vector<int> nums(diff_nums.size(), 0);
        nums[0] = diff_nums[0];
        if (nums[0] > capacity) return false;
        for (int i = 1; i < diff_nums.size(); i++) {
            nums[i] = nums[i - 1] + diff_nums[i];
            if (nums[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
20
21
22
23

6317. 统计美丽子数组数目 Medium 前缀异或和 2023/3/12

给你一个下标从 0 开始的整数数组nums 。每次操作中，你可以：
选择两个满足 0 <= i, j < nums.length 的不同下标 i 和 j 。
选择一个非负整数 k ，满足 nums[i] 和 nums[j] 在二进制下的第 k 位（下标编号从 0 开始）是 1 。
将 nums[i] 和 nums[j] 都减去 2^k 。
如果一个子数组内执行上述操作若干次后，该子数组可以变成一个全为 0 的数组，那么我们称它是一个美丽的子数组。
请你返回数组 nums 中美丽子数组的数目。
子数组是一个数组中一段连续非空的元素序列。
示例：
输入：nums = [4,3,1,2,4]
输出：2
解释：nums 中有 2 个美丽子数组：[3,1,2] 和 [4,3,1,2,4]

跳出连续子数组即滑动窗口的误区，本题中美丽子数组其所有元素化为二进制后，每一位出现的次数必为2的倍数，其总的异或结果必为0，故构建类似前缀和的前缀异或数组，将一段连续数的异或和转化为两个数的异或。例如 $n u m s$ 的子数组 $[3, 1, 2]$ 的异或和就可以用 $s [4] \oplus s [1] = 4 \oplus 4 = 0$ 算出来。构建完成后，只需从左到右遍历该数组，并使用map记录，出现相同数字则说明其这一段异或和为0。

class Solution {
public:
    long long beautifulSubarrays(vector<int> &nums) {
        long long ans = 0;
        int n = nums.size();
        vector<int> s(n + 1, 0); // 前缀异或数组
        for (int i = 0; i < n; ++i)
            s[i + 1] = s[i] ^ nums[i];
        unordered_map<int, int> cnt;
        for (int x : s)
            // 先计入答案再统计个数，如果反过来的话，就相当于把空子数组也计入答案了
            ans += cnt[x]++;
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/很楠不爱3/article/detail/87199

力扣方法总结：前缀和、树状数组、差分数组_力扣 树上差分