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

一维数组中的前缀和

题目1：区域和检索-数组不可变

给定一个整数数组 nums，求出数组从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j两点。

实现 NumArray类

NumArray(int[] nums) 使用数组 nums初始化对象

int sumRange(int i, int j) 返回数组 nums 从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点（也就是 sum(nums[i], nums[i + 1], ... , nums[j])）

输入：
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
输出：
[null, 1, -1, -3]
解释：
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)
numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1)) 
numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/range-sum-query-immutable
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目要求实现这个类：

class NumArray {
public:
    NumArray(vector<int>& nums) {

    }

    int sumRange(int left, int right) {

    }
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * int param_1 = obj->sumRange(left,right);
 */

sumRange函数需要计算并返回一个索引区间内的元素和，不用前缀和可以如下写代码：

class NumArray {
public:
    vector<int> nums;
    NumArray(vector<int>& nums) {
        this->nums = nums;
    }

    int sumRange(int left, int right) {
        int res = 0;
        for (int i = left; i <= right; ++i)
            res += nums[i];
        return res;
    }
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * int param_1 = obj->sumRange(left,right);
 */

这样是可以达到效果的，但是效率很差，因为 sumRange函数会被频繁调用，它的时间复杂度为 O(N)，其中 N代表 nums的长度。这题的最优解是使用前缀和，将 sumRange 函数的时间复杂度将为 O(1)，即不要在 sumRange 里面用 for 循环。代码如下：

class NumArray {
public:
    // 前缀和数组
    vector<int> preSum;
    NumArray(vector<int>& nums) {
        preSum.resize(nums.size() + 1, 0);
        // 计算 nums 累计和
        for (int i = 1; i < preSum.size(); ++i) 
            preSum[i] = preSum[i - 1] + nums[i - 1];
    }

    int sumRange(int left, int right) {
        return preSum[right + 1] - preSum[left];
    }
};

核心思路就是新建一个数组 preSum ，该数组 preSum[i] 记录nums[0...i - 1] 的累加和。 如图所示：

看这个 preSum 数组，如果我想求索引区间 [1, 4] 内的所有元素之和，就可以通过 preSum[5] - preSum[1] 得出。 这样，sumRange 函数仅仅需要做⼀次减法运算，避免了每次进⾏ for 循环调⽤，最坏时间复杂度为常数 O(1)。

注意：要特别注意 preSum 下标和给的参数不是完全一致的。

二维矩阵中的前缀和

题目 1：二位区域和检索-矩阵不变性

给定一个二维矩阵 matrix，以下类型的多个请求：

计算其子矩形范围内元素的总和，该子矩阵的 左上角 为 (row1, col1) ，右下角 为 (row2, col2) 。

实现 NumMatrix 类：

• NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
• int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1) 、右下角 (row2, col2) 所描述的子矩阵的元素总和 。

输入: 
["NumMatrix","sumRegion","sumRegion","sumRegion"]
[[[[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]]
输出: 
[null, 8, 11, 12]

解释:
NumMatrix numMatrix = new NumMatrix([[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (红色矩形框的元素总和)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (绿色矩形框的元素总和)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (蓝色矩形框的元素总和)

来源：力扣（LeetCode）
链接：[https://leetcode-cn.com/problems/range-sum-query-2d-immutable](https://leetcode-cn.com/problems/range-sum-query-2d-immutable)
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

比如输入的矩阵如下图：

那么，sumRegion(2, 1, 4, 3)就是图中红色矩形框的元素总和。本题还是前缀和的思想，如下图：

如果想要计算图中红色的子矩阵元素之和，可以用 绿色矩阵 - 蓝色矩阵 - 橙色矩阵 + 粉色矩阵 ，这 4 个矩阵的左上角都是 (0, 0) 原点。所以可以维护一个二维 preSum 数组，专门记录以原点位顶点的矩阵元素之和。求解 preSum 可以参考下图：

按照上述定义，preSum[i][j] 表示从 [0, 0] 到 [i][j] 的子矩阵元素之和。所以可以分析出：

所以要求 preSum[i][j] 表示，对应一下的递归公式：

在具体实现时，preSum 比原矩阵多一行一列，是为了让第 0 行和第 0 列的元素也可以使用递推公式。

class NumMatrix {
public:
  vector<vector<int>> preSum;
  NumMatrix(vector<vector<int>>& matrix) {
  int m = matrix.size(), n = matrix[0].size();
    preSum.resize(m + 1, vector<int>(n + 1, 0));
    // 注意，下标从 1 开始
    for(int i = 1; i <= m; ++i) {
      for(int j = 1; j <= n; ++j) {
        preSum[i][j] = preSum[i][j - 1] + preSum[i - 1][j] - preSum[i - 1][j - 1] + matrix[i - 1][j - 1];
      }
    }
  }
  int sumRegion(int row1, int col1, int row2, int col2) {
    return preSum[row2 + 1][col2 + 1] - preSum[row1][col2 + 1] - preSum[row2 + 1][col1] + preSum[row1][col1];
  }
};

/**

  - Your NumMatrix object will be instantiated and called as such:

  - NumMatrix* obj = new NumMatrix(matrix);

  - int param_1 = obj->sumRegion(row1,col1,row2,col2);

  */

和为 k 的子数组

题目 1：和为 k 的子数组

给你一个整数数组 nums 和一个整数 k，请你统计并返回该数组中和为 k 的连续子数组的个数。

输入：nums = [1,1,1], k = 2
输出：2

输入：nums = [1,2,3], k = 3
输出：2
来源：力扣（LeetCode）
链接：[https://leetcode-cn.com/problems/subarray-sum-equals-k](https://leetcode-cn.com/problems/subarray-sum-equals-k)
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

可以将所有的子数组穷举出来，看谁的和等于 k 就可以了。可以借助前缀和技巧。算法如下：

int subarraySum(vector<int>& nums, int k) {
  int len = nums.size();
  // 构造前缀和
  vector<int> preSum(len + 1, 0);
  for (int i = 1; i <= len; ++i) {
    preSum[i] = preSum[i - 1] + nums[i - 1];
  }
  int count = 0;
  // 穷举所有子数组
  for (int i = 1; i <= len; ++i) {
    for (int j = 0; j < i; ++j) {
      if (preSum[i] - preSum[j] == k)
        count++;
    }
  }
  return count;
}

该算法的时间复杂度为 O(N2) 空间复杂度为 O(N)。上述代码中有一个嵌套的 for 循环。第二层的 for 循环是在计算，有几个 j 能够使得 preSum[i] 和 preSum[j] 的差为 k 。每找到一个这样的j ，就把结果 +1。可以将 for 循环中的条件改变一下：

if (preSum[j] == preSum[i] - k)
  count++;

可以直接记录有几个 preSum[j] 和 preSum[i] - k 相等，直接更新结果，可以避免了内层的 for 循环。可以使用哈希表，记录前缀和和其出现的次数。

int subarraySum(vector<int>& nums, int k) {
  int len = nums.size();
  int preSum = 0, count = 0;
  unordered_map<int, int> mp;
  map[0] = 1;
  for (int i = 0; i <= len; ++i) {
    preSum += nums[i];
    int other = preSum - k;
    if (mp.find(other) != mp.end()) {
      count += mp[other];
    }
    mp[preSum]++;
  }
  return count;
}