前缀和是什么？

1.基础应用

2.联合应用

3.扩展应用

---

前缀和数组:

在这个数组中，每个元素表示原数组从第一个元素到当前元素的所有元素的和。

例如，如果原数组是 `a=[1, 2, 3, 4, 5]`，那么对应的前缀和数组就是 `s=[1, 3, 6, 10, 15]`。这是因为：

`s[0] = 1`（原数组的第一个元素）
`s[1] = s[0] + 2 = 3`（原数组的前两个元素的和）
`s[2] = s[1] + 3 = 6`（原数组的前三個元素的和）
`s[3] = s[2] + 4 = 10`（原数组的前四个元素的和）
`s[4] = s[3] + 5 = 15`（原数组的前五个元素的和）

那么我想知道在 a 某一段数组区间内 [ i , j ] 的和就可以用 s[ j ] - s[ i-1 ]直接求出了。

---

应用1：

【leetcode303 】给定一个整数数组  nums。计算索引left和right（包含left和right）之间的nums元素和，其中 left <= right。

思路与答案：最简单的前缀和算法了：

class NumArray {
public:
    vector<int>presum;
    NumArray(vector<int>& nums) {
        int n=nums.size();
        presum.resize(n+1);
        for(int i=0;i<presum.size();i++){
            presum[i+1]=presum[i]+nums[i];
        }
    }
    
    int sumRange(int left, int right) {
        return presum[j+1]-presums[i];
    }
};

【leetcode525】给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。

思路与转化：一提到最长连续子数组，就要考虑到前缀和；那么如何把前缀和和相同数量的0和1进行关联？也就是说在某一段区间内0的个数减去（-）1的个数等于0；相反数有这个特点，所以考虑到若把0看做是-1，把1看做是1。那么从第一个元素开始，数组的前缀和等于0的时候就是数量相等的时候了，但是空间的边界并不一定是从下标为0开始的，所以我们需要稍微转换一下。若两个区间 [0， i]和[0 , j ] 的前缀和差值为0，则说明 [0,j]的和 减去从[ 0, i ]的和，结果是0,即区间【i,j】中0和1个数相同。so，我们找前缀和数组中相同元素对应的下标作差，下标差最大的就是我们要找的答案。那么找下标差最大的：假设有多个相同的元素a，从后往前，即若下标 j （等于a的）确定下来了，找离他最远的那个 i（等于a的） 即可。最远的 i 应该是当 a 第一次出现的时候的i 。所以我们在遍历前缀和数组时，要先把这个i 和a记录下来，然后继续遍历前缀和数组，若遇到相同的a则把此时的下标取出来，做差。这种思路要用到哈希表哦，把 a 当做是索引，a对应的元素内容就是前缀和数组中的a元素的第一次出现的下标i。好，我们作差之后，更新最大序列长度。即要做的工作：一边遍历，一边录入最新的位置信息，一边作差找最大值。下图中的prefix sums就是哈希表了，存储的是sum中元素第一次出现的下标索引，ans就是遍历的时候a对应的下标差值。

实现部分，我们发现a[]和sum[]在实际情况下，可以用一个count变量存储sum每个元素就行（+1-1），遍历过程中用哈希表存储每个sum第一次出现的下标。注意，哈希表的初始化即空的前缀的结束下标为-1，先存入键值对（0，-1）意思就是现在哈希表的0号下标处填上-1，方便计算长度。例如，num=[1,0,1,0],则a=[1,-1,1,-1],sum=[1,0,1,0],把sum写入哈希表。当遍历到第二个元素得到sum为 0 时，通过哈希表中预先存好的 (0, -1) ，就能计算出从数组起始位置到当前位置这个子数组的长度为 1 - (-1) = 2 ，如果没有预先存入这个键值对，就无法正确计算这种从起始位置开始的满足条件的子数组长度。

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        // 初始化哈希表，存入键值对 (0, -1)
        unordered_map<int, int> hashmap;
        hashmap[0] = -1;

        int count = 0;  // 前缀和
        int max_length = 0;  // 最大长度

        for (int i = 0; i < nums.size(); ++i) {
            // 将 0 视为 -1
            if (nums[i] == 0) {
                --count;
            } else {
                ++count;
            }

            // 如果当前前缀和已经在哈希表中出现过
            if (hashmap.find(count) != hashmap.end()) {//hashmap.count(count)==1也行，因为.count()返回0或者1，常用于检测哈希表中是否存在某个索引值
                // 计算满足条件的子数组的长度
                int length = i - hashmap[count];
                // 更新最大长度
                max_length = max(max_length, length);
            } else {
                // 当前数字没出现过，记录当前前缀和第一次出现的下标
                hashmap[count] = i;
            }
        }

        return max_length;
    }
};

int main() {
    vector<int> nums = {0, 1};
    Solution solution;
    int result = solution.findMaxLength(nums);
    cout << "最长连续子数组的长度: " << result << endl;
    return 0;
}

应用2：

【leetcode560】给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。子数组是数组中元素的连续非空序列。

思路和算法：1.利用枚举 

#include <iostream>
#include <vector>

class Solution {
public:
    int subarraySum(std::vector<int>& nums, int k) {
        int n = nums.size();
        // 前缀和数组，长度为 n + 1，presum[0] 初始化为 0
        std::vector<int> presum(n + 1, 0);
        int count = 0;

        // 计算前缀和数组
        for (int i = 0; i < n; ++i) {
            presum[i + 1] = presum[i] + nums[i];
        }

        // 枚举所有可能的子数组
        for (int i = 0; i < n; ++i) {
            for (int j = i; j < n; ++j) {
                // 计算子数组 [i, j] 的和
                if (presum[j + 1] - presum[i] == k) {
                    count++;
                }
            }
        }
        return count;
    }
};

int main() {
    std::vector<int> nums = {1, 1, 1};
    int k = 2;
    Solution solution;
    int result = solution.subarraySum(nums, k);
    std::cout << "和为 " << k << " 的连续子数组个数为: " << result << std::endl;
    return 0;
}

这种方法时间复杂度是O(n^2)，所以采用前缀和+哈希表能够做到。哈希表用来存储每个前缀和出现的次数，利用当前的前缀和与k之间的关系计算满足条件的子数组个数。

2.利用前缀和+哈希表

我们考虑以 j 结尾的和为 k 的连续子数组个数时，只要统计有多少个前缀和为 pre[i]−k 的 pre[j] 即可。我们建立哈希表 mp，以和为键，出现次数为对应的值，记录 pre[j] 出现的次数，从左往右,边更新 mp ,边计算答案，那么以 j 结尾的答案 mp[pre[j]−k] 即可在 O(1) 时间内得到。将这些满足条件的mp值加起来就是最终答案。

#include <iostream>
#include <vector>
#include <unordered_map>

class Solution {
public:
    int subarraySum(std::vector<int>& nums, int k) {
        int count = 0;
        int sum = 0;
        // 哈希表，记录前缀和及其出现的次数
        std::unordered_map<int, int> prefixSumCount;
        // 初始化前缀和为 0 的情况出现 1 次
        prefixSumCount[0] = 1;

        for (int num : nums) {
            sum += num;
            // 如果 sum - k 存在于哈希表中，说明存在和为 k 的子数组
            if (prefixSumCount.find(sum - k) != prefixSumCount.end()) {
                count += prefixSumCount[sum - k];
            }
            // 更新当前前缀和的出现次数
            prefixSumCount[sum]++;
        }
        return count;
    }
};

int main() {
    std::vector<int> nums = {1, 1, 1};
    int k = 2;
    Solution solution;
    int result = solution.subarraySum(nums, k);
    std::cout << "和为 " << k << " 的连续子数组个数为: " << result << std::endl;
    return 0;
}

应用3差分：

1.二维前缀和公式：s[i][j] = a[i] [j] + s[i - 1][j] + s[i][j - 1 ] - s[i - 1][j - 1]

2.以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
s[x2, y2] - s[x1 - 1, y2] - s[x2, y1 - 1] + s[x1 - 1, y1 - 1]

差分：前缀和的逆运算过程。

原理：设有原数组 a[1..n]，我们构造一个差分数组 d[1..n]：

差分数组构建：

d[i]=a[i]−a[i−1]（通常令 a[0]=0，避免越界）

将区间 [l, r] 中的所有元素加上 x:

d[l] += x;
d[r+1] -= x;

a[1] = d[1];
for(int i = 2; i <= n; ++i)
    a[i] = a[i-1] + d[i];