前缀和

1. 一维前缀和

定义：对于数组 a，计算它的长为 n+1 的前缀和数组 s，即 a 的前 0 个数的和，前 1 个数的和，前 2 个数的和……前 n 个数的和。

s[0] = 0
s[1] = a[0]
s[2] = a[0]+a[1]
  ⋮
s[i] = a[0]+a[1]+⋯+a[i−1]
  ⋮
s[n] = a[0]+a[1]+⋯+a[n−1]
例如：数组 a = [−2,0,3,−5,2,−1]，对应的前缀和数组 s = [0,−2,−2,1,−4,−2,−3]

2. 二维前缀和

2559.统计范围内的元音字符串数

题目：给你一个下标从 0 开始的字符串数组 words 以及一个二维整数数组 queries。每个查询 queries[i] = [li, ri] 会要求我们统计在 words 中下标在 li 到 ri 范围内（包含这两个值）并且以元音开头和结尾的字符串的数目。返回一个整数数组，其中数组的第 i 个元素对应第 i 个查询的答案。

示例：输入：words = ["aba","bcb","ece","aa","e"], queries = [[0,2],[1,4],[1,1]]
输出：[2,3,0]
解释：以元音开头和结尾的字符串是 "aba"、"ece"、"aa" 和 "e"，查询 [0,2] 结果为 2（字符串 "aba" 和 "ece"）。查询 [1,4] 结果为 3（字符串 "ece"、"aa"、"e"）。查询 [1,1] 结果为 0。返回结果 [2,3,0]

class Solution {
public:
    bool isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }

    bool isVowelStr(string s) {
        int n = s.size();
        return isVowel(s[0]) && isVowel(s[n - 1]);
    }

    vector<int> vowelStrings(vector<string>& words,
                             vector<vector<int>>& queries) {
        int n = words.size();
        int m = queries.size();
        vector<int> prefixSum(n + 1, 0);
        vector<int> ans(m, 0);
        for (int i = 1; i < n + 1; i++) {
            prefixSum[i] =
                prefixSum[i - 1] + (isVowelStr(words[i - 1]) ? 1 : 0);
        }
        for (int i = 0; i < m; i++) {
            ans[i] = prefixSum[queries[i][1] + 1] - prefixSum[queries[i][0]];
        }
        return ans;
    }
};

1749.任意子数组和的绝对值的最大值

题目：给你一个整数数组 nums 。一个子数组 [numsl, numsl+1, ..., numsr-1, numsr] 的 和的绝对值 为 abs(numsl + numsl+1 + ... + numsr-1 + numsr)。请你找出 nums 中和的绝对值 最大的任意子数组（可能为空），并返回该最大值。

class Solution {
public:
    int maxAbsoluteSum(vector<int>& nums) {
        int n = nums.size();
        int preMax = 0, preMin = 0;
        vector<int> prefixSum(n + 1, 0);
        for (int i = 1; i < n + 1; i++) {
            prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
            preMax = max(preMax, prefixSum[i]);
            preMin = min(preMin, prefixSum[i]);
        }

        return preMax - preMin;
    }
};

523.连续的子数组和

题目：给你一个整数数组 nums 和一个整数 k ，如果 nums 有一个好的子数组返回 true ，否则返回 false：一个好的子数组是：长度至少为 2，且子数组元素总和为 k 的倍数。

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> m = {{0, -1}};
        int sum = 0;
        // prefixSums[q] − prefixSums[p] 为 k 的倍数时
        // prefixSums[p] 和 prefixSums[q] 除以 k 的余数相同

        for (int i = 0; i < nums.size(); ++i) {
            sum = (sum + nums[i]) % k;
            if (m.count(sum)) {
                int pos = m[sum];
                if ((i - pos) >= 2)
                    return true;
            } else
                m[sum] = i;
        }
        return false;
    }
};

304.二维区域和检索 - 矩阵不可变

题目：给定一个二维矩阵 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 {
    vector<vector<int>> sum;
public:
    NumMatrix(vector<vector<int>> &matrix) {
        int m = matrix.size(), n = matrix[0].size();
        sum.resize(m + 1, vector<int>(n + 1));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + matrix[i][j];
            }
        }
    }

    // 返回左上角在 (r1,c1) 右下角在 (r2,c2) 的子矩阵元素和
    int sumRegion(int r1, int c1, int r2, int c2) {
        return sum[r2 + 1][c2 + 1] - sum[r2 + 1][c1] - sum[r1][c2 + 1] + sum[r1][c1];
    }
};

差分

公式：$\sin \alpha + \sin \beta =2 \sin \frac{\alpha + \beta}{2}\cos \frac{\alpha - \beta}{2}$

对于数组 a，定义其差分数组（difference array）为

d[i]=

• a[0],i = 0
• a[i]−a[i−1],i >= 1 ​

​

1. 性质 1：从左到右累加 d 中的元素，可以得到数组 a。
2. 性质 2：如下两个操作是等价的。

• 把 a 的子数组 a[i],a[i+1],…,a[j] 都加上 x。
• 把 d[i] 增加 x，把 d[j+1] 减少 x。

例如：数组 a=[1,3,3,5,8]，对其中的相邻元素两两作差（右边减左边），得到数组 [2,0,2,3]。然后在开头补上 a[0]，得到差分数组 d=[1,2,0,2,3]

1094.拼车

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

示例：输入：trips = [[2,1,5],[3,3,7]], capacity = 4 输出：false

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        int n = trips.size();
        vector<int> diffArray(1001, 0);
        for (auto& trip : trips) {
            int num = trip[0], from = trip[1], to = trip[2];
            diffArray[from] += num;
            diffArray[to] -= num;
        }
        int cap = 0;
        for (int& diff : diffArray) {
            cap += diff;
            if (cap > capacity)
                return false;
        }
        return true;
    }
};

字典树