【动态规划】（五）前缀和

在之前的很多题目中其实已经用到了前缀和，前缀和是一种查询数组中任意区间的元素的和的数据结构，这里数组给定之后就不变了。针对这个不变的数组，前缀和用于多次查询区间 [i, j] 上元素的和。
前缀和的推导和计算隐含着动态规划的基本思想，同时它的状态设计是线性动态规划中比较简单的那一类。与线性动态规划一样，前缀和也有一维和二维两种场景。
虽然前缀和本身很简单，但需要用到它解决的问题非常多，与其它数据结构配合的变化也很多，因此需要从线性动态规划中剥离出来单独学习。

前缀和最简单的应用就是求区间和，我们之前在动态规划问题中也遇到不少，比如求数组分组的最大分数，就要预先计算前缀和以方便快速求出任意区间的平均值。
前缀和除了求区间和之外，还有一些其它的应用：

在用动态规划的方式推 sums[i] 的时候，有时求完 sums[i] 需要查询以前算过的结果计算某种指标，需要用其它数据结构将前面的计算结果维护起来，例如哈希表等等，在求每个位置的前缀和的过程中，查询数据结构并更新答案，这是前缀和的一大类问题，变化比较多，力扣上这类题也有很多
前缀和的逆运算是差分，对原序列求出其差分序列，然后再对得到的差分序列求其前缀和序列，可以得到原序列，这在处理一些区间修改的问题时很有用
前缀和还可以推广到二维上，并用于快速求矩形和，二维前缀和的计算过程是最经典的矩阵上的线性动态规划

接下来我们对这几类题目分别进行总结梳理。

1 实现前缀和

为了加深对前缀和的理解，还是先从最基础的前缀和用于求区间和开始，虽然题目很简单，但这两道题的思想就是后面的各种变体题目中会反复用到的，因此一定要熟练掌握。

实现一维前缀和：区域和检索

实现二维前缀和：二维区域和检索

二维前缀和需要注意：不要使用一维前缀和先计算每一行前缀和再把每一行结果加起来，这样就违背了前缀和可以在 O(1) 时间内找到区间和的性质，要用二维整体思想维护前缀和。

2 数据结构维护前缀和

前缀和最常见的一大类问题是：在用动态规划的方式计算前缀和 sums[i] 的时候，求完 sums[i] 需要查询以前算过的结果来计算某种指标，需要用其它数据结构将前面的计算结果维护起来，以便高效查询。

提到高效查询自然最常用的就是哈希表，这类题目非常多，变化纷繁复杂，这里我们按几大类进行梳理。

2.1 哈希表维护前缀和第一类

最简单的一类哈希表维护前缀和问题，这类问题中，key为前缀和的值，value为前缀和第一次出现时的下标。

和等于 k 的最长子数组长度

给定一个数组 nums 和一个目标值 k，找到和等于 k 的最长连续子数组长度。如果不存在任意一个符合要求的子数组，则返回 0。

需要注意几个细节，哈希表要记录前缀和第一次出现的下标，因为这样才能保证长度更长；初始化前缀和 0 的下标设为 -1 .

class Solution {
public:
    int maxSubArrayLen(vector<int>& nums, int k) {
        int sum = 0, ans = 0;
        unordered_map<int,int> map;
        map[0] = -1;
        for(int i = 0; i < nums.size(); ++i)
        {
            sum += nums[i];
            if(map.count(sum - k))
            {
                ans = max(ans, i - map[sum - k]);
            }
            if(!map.count(sum))
            {
                map[sum] = i;
            }
        }
        return ans;
    }
};

连续数组

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

题目本身看起来不难，但按正常思路就是很难做。难点在于问题转换，如果把 0 看成 -1，那么问题就转化成了上一题，求和等于 k 的最长子数组长度，这里 k = 0，这就变得无比简单了。

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int sum = 0, ans = 0;
        unordered_map<int, int> map;
        map[0] = -1;
        for(int i = 0; i < nums.size(); ++i)
        {
            sum += nums[i] == 0 ? -1 : 1;
            if(map.count(sum))
            {
                ans = max(ans, i - map[sum]);
            }
            else{
                map[sum] = i;
            }
        }
        return ans;
    }
};

每个元音包含偶数次的最长子字符串

给你一个字符串 s ，请你返回满足以下条件的最长子字符串的长度：每个元音字母，即 ‘a’，’e’，’i’，’o’，’u’ ，在子字符串中都恰好出现了偶数次。

这道题考查的内容非常丰富，而且非常巧妙，能想到用前缀和解决已经不容易，但是用前缀和如何解决更是一个问题。

我们当然可以为每一个元音字母维护一个前缀和，然后对于每个区间判断五个前缀和都满足条件就更新最长长度，但这样也要遍历全部子区间，时间复杂度太高，因为题目没有给出字母出现多少次这样的限制，只说了出现偶数次，越多越好，这导致我们没有一个恒定的关系式去进行查找（像前两道题中，告诉了我们和为 k，我们就有一个关系式去哈希表中查找了）。

这道题巧妙的地方就在于此，我们还有一个很简单但不容易想到的性质没有充分利用：我们需要找的子串中，每个元音字母都恰好出现了偶数次，而奇数减奇数等于偶数，偶数减偶数等于偶数。也就是说只要每个元音字母的前缀和中两个位置的奇偶性相同，那么这个字母在这两个前缀和区间内就一定出现了偶数次，因此我们只要找到前缀和中和当前奇偶性相同的最小的下标就行了，因此每个元音字母的前缀和中我们只要记录它最早出现奇数次的下标和最早出现偶数次的下标就行了，然后向后扫描，出现奇数次就减去奇数次下标，偶数次就减去偶数次下标，这样就能保证是一个元音字母出现了偶数次的最长的子序列。但我们要同时考虑五个元音字母，如果用五个前缀和来维护再去判断依然很麻烦，因此还需要进一步优化。

我们可以把五个字母一起考虑，同时记录五个字母出现次数的奇偶性，扫描字符串的过程中每一个位置都可以记录以当前位置结尾的子字符串中五个元音字母出现次数的奇偶性，当五个元音字母出现次数的奇偶性和之前某一位置完全一致的时候，这两个位置之间的子字符串中，五个元音字母就都出现了偶数次。因为每个元音字母只有出现奇数次和出现偶数次两种状态，因此可以用 0 表示出现偶数次，用 1 表示出现奇数次，那么五个字母每一个都有 0 和 1 两种状态，组合起来就一共有 $2^5=32$ 种状态，我们可以用一个二进制数的每一位表示一个元音字母的奇偶性，那么我们只要 00000 到 11111 之间的32个数就可以描述所有的状态，因此哈希表也不需要了，只要用一个长度为 32 的数组 states 来记录就可以，数组中每一个位置对应一种状态，存储的内容就是这个状态第一次出现时的下标。

初始时所有字母都出现零次，因此 00000 状态对应的最早出现的下标就是 0，所以数组 states[0] = 0。这样一来我们只需要遍历一次字符串，并且只需要使用常数空间就可以解决问题。

这道题目非常巧妙，值得反复推敲，并且编码的时候注意灵活运用常见的位运算，比如每次出现一个相同的元音字母，它出现次数的奇偶性就会反转，奇数变偶数，偶数变奇数，这里用异或操作很容易实现，可以用当前状态和这个元音字母对应位置为 1 的状态异或就可以达到指定位置翻转的效果。

class Solution {
public:
    int findTheLongestSubstring(string s) {
        int ans = 0, status = 0, n = s.length();
        vector<int> pos(1 << 5, -1);
        pos[0] = 0;
        for (int i = 0; i < n; ++i) {
            if (s[i] == 'a') {
                status ^= 1<<0;
            } else if (s[i] == 'e') {
                status ^= 1<<1;
            } else if (s[i] == 'i') {
                status ^= 1<<2;
            } else if (s[i] == 'o') {
                status ^= 1<<3;
            } else if (s[i] == 'u') {
                status ^= 1<<4;
            }
            if (~pos[status]) {
                ans = max(ans, i + 1 - pos[status]);
            } else {
                pos[status] = i + 1;
            }
        }
        return ans;
    }
};

2.2 哈希表维护前缀和第二类

这类问题中，key是前缀和（前缀状态）的值，value为前缀和或状态出现的次数。

和为 K 的子数组

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

与“和为 k 的最长子数组长度”完全一样的思路，只是这次维护的哈希表中要记录当前的前缀和出现的次数。

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int sum = 0, ans = 0;
        unordered_map<int,int> map;
        map[0] = 1;
        for(int i = 0; i < nums.size(); ++i)
        {
            sum += nums[i];
            if(map.count(sum-k))
            {
                ans += map[sum-k];
            }
            map[sum]++;
        }
        return ans;
    }
};

统计「优美子数组」

给你一个整数数组 nums 和一个整数 k。如果某个连续子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。

请返回这个数组中「优美子数组」的数目。

同样进行问题转化，如果把奇数看作1，偶数看作0，那么这道题就是和上一题一样的找到和为 k 的最大连续子数组的个数。直接把代码复制下来改个条件即可。

class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        int sum = 0, ans = 0;
        unordered_map<int,int> map;
        map[0] = 1;
        for(int i = 0; i < nums.size(); ++i)
        {
            sum += nums[i] & 1;
            if(map.count(sum-k))
            {
                ans += map[sum-k];
            }
            map[sum]++;
        }
        return ans;
    }
};

当然这道题还有优化的空间，完全可以用一个数组 cnt 代替哈希表记录前缀和出现的次数，数组每一项都初始化为 0，哈希表的 map.count(sum-k) 就等价于 cnt[sum-k] > 0，当然要注意数组下标越界问题，要使map[sum-k] > 0首先得有 sum >= k，因为sum 比 k 小的时候说明数组还不够 k 个奇数，此时 map[sum-k] 表示出现了负数个奇数的下标数量，那一定是0，而当sum >= k 时，如果 map[sum-k] 有值我们就加到结果中，没有值即为 0 ，也可以直接加到结果中，综上，代码非常简洁：

class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        int ans = 0, sum = 0;
        vector<int> cnt(nums.size()+1, 0);  //相当于哈希表
        cnt[0] = 1;
        for(int i = 0; i < nums.size(); ++i)
        {
            sum += nums[i] & 1;
            ans += sum >= k ? cnt[sum-k] : 0;
            cnt[sum]++;
        }
        return ans;
    }
};

2.3 哈希表维护前缀和第三类

这一类问题中，key是前缀和模 K 的余数（可以理解为前缀状态，状态为前缀和模 K）,value可能是最早出现的下标，也可能是出现的次数。

连续的子数组和

给你一个整数数组 nums 和一个整数 k ，编写一个函数来判断该数组是否存在同时满足下述条件的连续子数组：

子数组大小至少为 2

子数组元素总和为 k 的整数倍

找好判定条件即可，这道题的判定条件的关键是数学上所谓的同余定理：如果两个数的差能被 k 整除，那么两个数关于 k 同余，同余即除以 k 的余数相同。因此前缀和计算关于 k 的余数，哈希表记录这个余数最早出现的下标。

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        int sum = 0;
        unordered_map<int, int> map;
        map[0] = -1;
        for(int i = 0; i < nums.size(); ++i)
        {
            sum += nums[i];
            int 
            if(map.count(sum % k) && i - map[sum % k] > 1)
            {
                return true;
            }
            if(!map.count(sum % k))
            {
                map[sum % k] = i;
            }
        }
        return false;
    }
};

和可被 K 整除的子数组

给定一个整数数组 nums 和一个整数 k ，返回其中元素之和可被 k 整除的（连续、非空） 子数组 的数目。

这道题现在这么一看就懂了，不赘述。直接上代码：

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        unordered_map<int, int> record = {{0, 1}};
        int sum = 0, ans = 0;
        for (int elem: nums) {
            sum += elem;
            //注意这里的取模运算处理
            int modulus = (sum % k + k) % k;
            if (record.count(modulus)) {
                ans += record[modulus];
            }
            ++record[modulus];
        }
        return ans;
    }
};

代码中取模运算为什么要写成那样呢，因为直接在上一题的代码上修改会发现无法通过全部测试用例，这是因为C++取模运算的特性导致的，C++中如果对负数取模，输出将会是负数，但我们在这道题中希望输出是正数，否则当输入 nums = [-1,2,9]，k = 2时，第一个前缀和的余数是 -1，第二个前缀和余数是 1 ，对除数 2 来说这两个余数是等价的，但我们却会判断他们不相等而导致错误计数，因此我们把所有余数都取正数以方便判断。

为什么C++对负数取余输出是负数？

这是一个经典的问题，用 C++ 或者 Java 语言计算 -7 % 3 得到的结果会是 -1，而 Python 中 -7 % 3 的结果为 2 ，当然答案都没问题，只是一个小于 0 ，一个大于 0 .

要了解结果不同的原因，首先要明白编程语言中是如何进行取模运算的：a % b = a - (a / b) * b

但是由于不同的计算机语言对于整数除法的处理不同，取模运算的结果也会不同。
在 C++ 和 Java 中，整数除法是向零取整除法，也就是结果向靠近零的数取整，因此 -7 / 3 = -2. 于是按照取模运算的算法：
1
2
-7 % 3 = -7 - (-7 / 3) * 3 = -7 - (-2) * 3 = -7 - (-6) = -1
7 % -3 = 7 - (7 / -3) * (-3) = 7 - (-2) * (-3) = 7 - 6 = 1
而在 Python 中，整数除法是向下取整除法，也就是结果取小于它的最大整数，因此 -7 / 3 = -3.于是按照取模运算的算法：
1
2
-7 % 3 = -7 - (-7 / 3) * 3 = -7 - (-3) * 3 = -7 - (-9) = 2
7 % -3 = 7 - (7 / -3) * (-3) = 7 - (-3) * (-3) = 7 - 9 = -2
所以是因为计算机语言对于整数除法的实现不同，导致了对于取模运算结果的不同。

2.4 同时维护前缀和与后缀和

在有些问题中，计算答案时同时需要用到前缀和和后缀和，下面是几道典型题目。

除自身以外数组的乘积

给你一个整数数组 nums，返回数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

请不要使用除法，且在 O(n) 时间复杂度内完成此题。

题目中明确说了不要使用除法，不单单是为了避免最简单的做法，而是用除法的话当数组中出现 0 时就会出错，因此是一种不安全的做法。

稍加思考就会发现这道题可以维护前缀积和后缀积很轻松地解决，前缀积也是前缀和的推广，后面会专门总结这一类型。

我们只要用前缀积记录 nums[i] 左侧所有数字的积，用后缀积记录 nums[i] 右侧所有数字的积，把同一位置的前缀积和后缀积相乘就是这个位置的结果了。

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> ans;
        vector<int> pre(nums.size(), 1);
        for(int i = 1; i < nums.size(); ++i)
        {
            pre[i] = pre[i-1] * nums[i-1];
        }
        vector<int> post(nums.size(), 1);
        for(int i = nums.size()-2; i >=0; --i)
        {
            post[i] = post[i+1] * nums[i+1];
        }
        for(int i = 0; i < nums.size(); ++i)
        {
            ans.push_back(pre[i] * post[i]);
        }
        return ans;
    }
};

当然这道题用两个数组分别存放前缀积和后缀积太奢侈了，完全可以用 O(1) 额外空间完成上面的过程，因为前缀积的计算只依赖它前一个位置的前缀积，因此可以把数组优化掉只用一个整数来记录，这也是动态规划的常规优化思路了，之前见了很多，所以我们直接用结果数组 ans 存放前缀积和后缀积，先从左到右遍历，再从右到左遍历，就可以计算出最终结果了。

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> ans(nums.size(),1);
        int pre = 1;
        for(int i = 1; i < nums.size(); ++i)
        {
            pre *= nums[i-1];
            ans[i] *= pre;
        }
        int post = 1;
        for(int i = nums.size() - 2; i >=0; --i)
        {
            post *= nums[i+1];
            ans[i] *= post;
        }
        return ans;
    }
};

寻找数组的中心下标

给你一个整数数组 nums ，请计算数组的中心下标 。
数组中心下标是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。
如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。

如果用前缀和方法的话，和上面的题目是一样的思路，就不多说了。当然这是一道简单题，还有更简单的做法，如果一个位置是中心下标，那么它左右两侧数字和相等，也就是说
$$
sum_{left} + nums[i] + sum_{right} = total \
由于 \ sum_{left} = sum_{right} \
于是 \ nums[i] + 2sum = total
$$
因此直接遍历每一个位置，动态的更新左侧数字和sum，判断是否满足上面的关系式就可以了。

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 + nums[i] == total) {
                return i;
            }
            sum += nums[i];
        }
        return -1;
    }
};

找两个和为目标值且不重叠的子数组

给你一个正整数数组 arr 和一个整数值 target 。
请你在 arr 中找 两个互不重叠的子数组 且它们的和都等于 target 。可能会有多种方案，请你返回满足要求的两个子数组长度和的最小值。
请返回满足要求的最小长度和，如果无法找到这样的两个子数组，请返回 -1 。

这道题考查的相当综合，我们可以用之前的前缀和方法计算出所有满足条件的子数组然后取长度最短的两个，问题在于如何判断这两个子数组不重叠。最简单的方法是记录每一个子数组的左右边界然后进行比对判断，但这样太麻烦了，如果我们只考虑一个边界呢？比如我们从左到右扫描数组，找到符合条件的子数组就记录它的右边界和区间长度，那么要使两个子数组不重叠就需要另一个子数组的右边界小于当前子数组右边界减去当前区间长度，与此同时还要保证这两个子数组长度总和最小，自然想到动态规划。

定义 $dp[i]$ 表示以第 i 个数为右边界的和为 target 的子数组的最小长度。那么如果我们在当前位置没找到满足条件的子数组，$dp[i]$ 就等于上一个位置 $dp[i-1]$；而当我们找到一个满足条件的
$$
dp[i] = min(len, dp[i-1])
$$
边界条件 $dp[0]$ 表示没有数字的子数组，无意义，但为了状态转移正确要初始化一个很大的值，为了避免计算溢出，只要比原数组长度大即可。

这样一来，我们最终需要的答案就是以当前位置为右边界的数组的最小长度 $dp[i]$ 加上和当前位置为右边界的最短子数组不重叠的子数组长度 $dp[i-len]$。

如果最终的结果比原数组长度大，那说明没有不重叠的子数组，返回 -1 .

class Solution {
public:
    int minSumOfLengths(vector<int>& arr, int target) {
        int ans = INT_MAX, sum = 0;
        unordered_map<int, int> map;
        map[0] = -1;
        vector<int> dp(arr.size()+1, 0);
        dp[0] = arr.size() + 1;
        for(int i = 0; i < arr.size(); ++i)
        {
            sum += arr[i];
            if(map.count(sum - target))
            {
                int len = i - map[sum-target];
                dp[i+1] = min(len, dp[i]);	//更新动态规划状态
                ans = min(ans, dp[i-len+1] + len);	//更新答案
            }
            else
            {
                dp[i+1] = dp[i];
            }
            map[sum] = i;
        }
        return ans > arr.size() ? -1 : ans;		//最终答案不能比原数组长度大
    }
};

这道题还有可优化的空间，因为题目中明确说了是正整数数组，因此我们不需要用前缀和去找满足条件的数组，可以用之前学过的双指针滑动窗口，因为数组内都是正整数，那么当滑动窗口扩大的时候和一定会增大，因此我们维护两个指针，初始时都指向 0 位置，然后右指针右移计算区间和，如果区间和小于target，说明数字不够，继续右移扩大窗口，当区间和大于 target 说明数字多了，左指针右移收缩窗口，当区间和等于 target 就找到了一个符合条件的子数组，然后按照上面的流程更新状态和答案即可。

class Solution {
public:
    int minSumOfLengths(vector<int>& arr, int target) {
        int n = arr.size(), left = 0, right, sum = 0, ans = INT_MAX;
        vector<int> dp(n + 1, 0);
        dp[0] = n + 1;
        for (right = 0; right < n; ++right) {
            sum += arr[right];
            while (sum > target) {
                sum -= arr[left++];
            }
            if (sum == target) {
                int len = right - left + 1;  
                dp[right + 1] = min(dp[right], len);
                ans = min(ans, len + dp[left]); 
            }
            else {
                dp[right + 1] = dp[right];
            }
        }
        return ans > n ? -1 : ans;
    }
};

2.5 数据结构维护前缀和：二维情况

元素和为目标值的子矩阵数量

给出矩阵 matrix 和目标值 target，返回元素总和等于目标值的非空子矩阵的数量。

子矩阵 (x1, y1, x2, y2) 是满足 x1 <= x <= x2 且 y1 <= y <= y2 的所有单元 matrix[x][y] 的集合。

如果 (x1, y1, x2, y2) 和 (x1', y1', x2', y2') 两个子矩阵中部分坐标不同（如：x1 != x1'），那么这两个子矩阵也不同。

按照之前的处理矩阵的经验，这道题可以通过枚举上下边界转化为一维的 “和为 K 的子数组” 问题，然后按照一维的方法做即可。

class Solution {
public:
    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
        int rows = matrix.size(), cols = matrix[0].size(), ans = 0;
        for(int i = 0; i < rows; ++i)
        {
            vector<int> sums(cols, 0);
            for(int j = i; j < rows; ++j)
            {
                for(int k = 0; k < cols; ++k)
                {
                    sums[k] += matrix[j][k];
                }
                int sum = 0;
                unordered_map<int, int> map;
                map[0] = 1;
                for(int k = 0; k < cols; ++k)
                {
                    sum += sums[k];
                    if(map.count(sum - target))
                    {
                        ans += map[sum - target];
                    }
                    map[sum]++;
                }
            }
        }
        return ans;
    }
};

矩阵区域和

给你一个 m x n 的矩阵 mat 和一个整数 k ，请你返回一个矩阵 answer ，其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和：

i - k <= r <= i + k,

j - k <= c <= j + k 且

(r, c) 在矩阵内。

回顾之前的二维前缀和计算，那么把问题转化为对数组 mat 中的每个位置，计算以 (i - K, j - K) 为左上角，(i + K, j + K) 为右下角的矩形子数组的元素之和，再利用维护好的二维前缀和就很好解决了，只要注意下标位置越界的判断即可。

class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        int rows = mat.size(), cols = mat[0].size();
        vector<vector<int>> pre(rows+1, vector<int>(cols+1, 0));
        for(int i = 1; i <= rows; ++i)
        {
            for(int j = 1; j <= cols; ++j)
            {
                pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + mat[i-1][j-1];
            }
        }
        vector<vector<int>> ans(rows, vector<int>(cols, 0));
        for(int i = 0; i < rows; ++i)
        {
            for(int j = 0; j < cols; ++j)
            {
                int endposx = min(i+k+1, rows);
                int endposy = min(j+k+1, cols);
                int beginposx = max(i-k, 0);
                int beginposy = max(j-k, 0);
                ans[i][j] = pre[endposx][endposy] - pre[beginposx][endposy] - pre[endposx][beginposy] + pre[beginposx][beginposy];
            }
        }
        return ans;
    }
};

最大子矩阵

给定一个正整数、负整数和 0 组成的 N × M 矩阵，编写代码找出元素总和最大的子矩阵。

返回一个数组 [r1, c1, r2, c2]，其中 r1, c1 分别代表子矩阵左上角的行号和列号，r2, c2 分别代表右下角的行号和列号。若有多个满足条件的子矩阵，返回任意一个均可。

之前做过的题目，现在再来看就非常简单了，同样是枚举上下边界转化为一维最大子数组问题。

class Solution {
public:
    vector<int> getMaxMatrix(vector<vector<int>>& matrix) {
        vector<int> ans(4);//保存最大子矩阵的左上角和右下角的行列坐标
        int N = matrix.size();
        int M = matrix[0].size();
        int maxsum=INT_MIN;//记录最大值
        int r1,c1;//暂时记录左上角，相当于begin
        for(int i = 0; i < N; i++){     //以i为上边，从上而下扫描
            vector<int> b(M, 0);    //记录当前i~j行组成大矩阵的每一列的和，将二维转化为一维
            for(int j = i; j < N; j++){    //子矩阵的下边，从i到N-1，不断增加子矩阵的高
                //每次循环都相当于求一次一维最大子序列和
                int dp = 0;
                for(int k = 0; k < M; k++){
                    b[k] += matrix[j][k];   
                    if(dp > 0){
                        dp += b[k];     //相当于dp[i] = dp[i-1] + nums[i]
                    }
                    else{
                        dp = b[k];      //相当于dp[i] = 0 + nums[i]
                        r1 = i;
                        c1 = k;
                    }
                    if( dp > maxsum){
                        maxsum = dp;
                        ans = {r1, c1, j, k};
                    }
                }
            }
        }
        return ans;
    }
};

矩形区域不超过 K 的最大数值和

给你一个 m x n 的矩阵 matrix 和一个整数 k ，找出并返回矩阵内部矩形区域的不超过 k 的最大数值和。

题目数据保证总会存在一个数值和不超过 k 的矩形区域。

也是之前做过的题目，现在看来同样是枚举上下边界转化为一维问题，难点在于对和不超过 k 的理解。我们在维护出的前缀和数组 sum 中要找到满足：
$$
sum[right]-sum[left] \leq k
$$
简单移项可以得到：
$$
sum[left] \geq sum[right]-k
$$
因此对于当前的 $sum[right]$ 来说，要找到满足上式的 $sum[left]$ ，同时为了保证 $sum[right]-sum[left]$ 尽可能大，我们找的满足条件的 $sum[left]$ 就要尽可能的小，然后结果取所有$sum[right]-sum[left]$ 中的最大值。

class Solution {
public:
    int maxSumSubmatrix(vector<vector<int>> &matrix, int k) {
        int ans = INT_MIN;
        int m = matrix.size(), n = matrix[0].size();
        for (int i = 0; i < m; ++i) { // 枚举上边界
            vector<int> sum(n);
            for (int j = i; j < m; ++j) { // 枚举下边界
                for (int c = 0; c < n; ++c) {
                    sum[c] += matrix[j][c]; // 更新每列的元素和
                }
                set<int> sumSet{0};		//用有序哈希表方便查找满足条件的最小值
                int s = 0;
                for (int v : sum) {
                    s += v;
                    auto lb = sumSet.lower_bound(s - k);	//查找满足条件的sum[left]中的最小值，即下边界
                    if (lb != sumSet.end()) {
                        ans = max(ans, s - *lb);	//取所有sum[right]-sum[left]中的最大值
                    }
                    sumSet.insert(s);
                }
            }
        }
        return ans;
    }
};

3 前缀和推广

前缀和求的是数组 a 的前缀 [0..i-1] 的和，也就是对这些元素做加法结果，实际上对前缀 [0..i-1]，我们还可以做很多其它运算得到相应结果。
如果利用前缀上的某种运算的结果，可以像前缀和一样快速得到区间 [L, R] 上同样运算的结果，那么前缀和就成功推广了。

事实上这种运算是存在的，例如之前我们遇到过的前缀积，也就是乘法运算，再例如异或运算，对应每个前缀 [0..i-1] ，我们都可以求得一个异或值，称为前缀异或，而对于区间 [L, R]。我们可以用 [0..R] 的前缀异或减去 [0..L-1] 的前缀异或就可以得到区间上的异或值，这个逻辑与前缀和完全相同。这依赖于异或运算的性质。

3.1 前缀积

乘积最大子数组

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

乘积最大子数组和加法的区别在于要考虑负数的的情况，为了让负数相乘的结果尽可能大，我们还要维护一个最小乘积。

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int dpmax = nums[0], dpmin = nums[0], ans = nums[0];
        for(int i = 1; i < nums.size(); i++)
        {
            int tmp = dpmax;
            dpmax = max(dpmax * nums[i], max(nums[i], dpmin * nums[i]));
            dpmin = min(tmp * nums[i], min(nums[i], dpmin * nums[i]));
            ans = max(ans, dpmax);
        }
        return ans;
    }
};

乘积小于K的子数组

给定一个正整数数组 nums和整数 k 。

请找出该数组内乘积小于 k 的连续的子数组的个数。

类似于矩形区域不超过K的子矩阵问题，相比之下还更简单一些。有时候我们可能直接去想一些优化后的算法不是那么容易，这时候我们就可以先按暴力的方法把代码写出来再观察。比如这道题我们就用最暴力的前缀积方法先把代码写出来，也不考虑额外空间，多重循环，乘积过大会溢出之类的问题：

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if(k == 0) return 0;
        int n = nums.size(), ans = 0;
        vector<int> pre(n+1,1);
        for(int i = 1; i <= n; ++i)
        {
            pre[i] = pre[i-1] * nums[i-1];
        }
        for(int i = 1; i <= n; ++i)
        {
            for(int j = 0; j < i; ++j)
            {
                if(pre[i] / pre[j] < k)
                {
                    ans += (i - j);
                    break;
                }
            }
        }
        return ans;
    }
};

当然这个方法是肯定无法通过测试的，但是我们观察代码可以获得更多的想法，因为题目给定的都是正整数，所以实际上在二重循环中我们只是在寻找 i 左边的使得 i 位置的前缀积能小于 k 的第一个 j ，那么之后的所有 j 就都可以和 i 形成一个乘积小于 k 的子区间，这不就是我们的优化方向吗。

这样一来也不需要使用数组维护前缀积了，上一次我们遇到正整数数组的时候用的是滑动窗口，那这里也是一样，对于每一个 right 指针指向的位置，如果它的前缀积不小 k ，那就说明数字多了，左移 left 指针收缩窗口，直到乘积小于 k ，那么 right 位置就可以提供 right - left + 1个乘积小于 k 的子数组。

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if(k == 0) return 0;
        int ans = 0, left = 0, plus = 1;
        for(int right = 0; right < nums.size(); ++right)
        {
            plus *= nums[right];
            while(plus >= k && left <= right)
            {
                plus /= nums[left];
                ++left;
            }
            ans += (right - left + 1);
        }
        return ans;
    }
};

最后 K 个数的乘积

请你实现一个「数字乘积类」ProductOfNumbers，要求支持下述两种方法：

add(int num)：将数字 num 添加到当前数字列表的最后面。

getProduct(int k)：返回当前数字列表中，最后 k 个数字的乘积。你可以假设当前列表中始终至少包含 k 个数字

简单的实现问题，注意对0的处理即可，当遇到数字0直接清空前缀积数组，如果要求的 k 大于当前的前缀积数组长度，说明后 k 个数中一定有 0，直接返回 0 即可，其他情况正常除法。

class ProductOfNumbers {
public:
    vector<int> pre;
    ProductOfNumbers() {
        pre.assign(1, 1);
    }
    
    void add(int num) {
        if(num == 0) pre.resize(1,1);
        else pre.push_back(pre.back()*num);
    }
    
    int getProduct(int k) {
        return k < pre.size() ? pre.back() / *(pre.end()- k - 1) : 0;
    }
};

3.2 前缀异或

子数组异或查询

有一个正整数数组 arr，现给你一个对应的查询数组 queries，其中 queries[i] = [Li, Ri]。

对于每个查询 i，请你计算从 Li 到 Ri 的 XOR 值（即 arr[Li] xor arr[Li+1] xor … xor arr[Ri]）作为本次查询的结果。

并返回一个包含给定查询 queries 所有结果的数组。

只要知道了前缀异或成立，这道题目没什么难度。借这道题证明为什么异或运算也满足区间减法：
$$
\begin{split}
Q(left, right) &= arr[left] \oplus … \oplus arr[right] \\
&= (arr[0] \oplus … \oplus arr[left-1]) \oplus (arr[0] \oplus … \oplus arr[left-1]) \oplus (arr[left] \oplus … \oplus arr[right])\\
&=(arr[0] \oplus … \oplus arr[left-1]) \oplus(arr[0] \oplus … \oplus arr[right]) \\
\end{split}
$$
这里用到了异或的结合律，实际上也正因为异或满足结合律所以可以满足区间减法的性质。

class Solution {
public:
    vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
        int n = arr.size();
        vector<int> xors(n + 1);
        for (int i = 0; i < n; i++) {
            xors[i + 1] = xors[i] ^ arr[i];
        }
        int m = queries.size();
        vector<int> ans(m);
        for (int i = 0; i < m; i++) {
            ans[i] = xors[queries[i][0]] ^ xors[queries[i][1] + 1];
        }
        return ans;
    }
};

形成两个异或相等数组的三元组数目

给你一个整数数组 arr 。现需要从数组中取三个下标 i、j 和 k ，其中 (0 <= i < j <= k < arr.length) 。

a 和 b 定义如下：

a = arr[i] ^ arr[i + 1] ^ … ^ arr[j - 1]

b = arr[j] ^ arr[j + 1] ^ … ^ arr[k]

请返回能够令 a == b 成立的三元组 (i, j , k) 的数目。

假设前缀异或数组为 $xors$，实际上 $a=xors[i] \oplus xors[j]$，$b=xors[j] \oplus xors[k+1]$，而 $a==b$，那也就是 $xors[i]==xors[k+1]$，因此只要找到前缀异或相等的两个位置 $i$ 和 $k$，这两个位置中的任意一个位置都可以是 $j$。

class Solution {
public:
    int countTriplets(vector<int> &arr) {
        int n = arr.size();
        unordered_map<int, int> cnt, total;
        int ans = 0, s = 0;
        for (int k = 0; k < n; ++k) {
            int val = arr[k];
            if (cnt.count(s ^ val)) {
                ans += cnt[s ^ val] * k - total[s ^ val];
            }
            ++cnt[s];
            total[s] += k;
            s ^= val;
        }
        return ans;
    }
};

4 差分

差分是对前缀和性质的一个巧妙运用，有时候能起到奇效。

前缀和序列 $S_{0}, S_{1}, …, S_{n}$ 的差分序列 $a_{0}, a_{1}, …, a_{n-1}$ 就等于原序列，其中 $a_{i} = S_{i+1} - S_{i}$ 。

原序列 $a_{0}, a_{1}, …, a_{n-1}$ 的差分序列为 $b_{0}, b_{1}, …, b_{n-1}$，其中 $b_{0} = a_{0} - 0, b_{i} = a_{i} - a_{i-1}$。则对差分序列求前缀和序列，就能得到原序列。

差分序列的好处是如果要对原序列的一个区间 $[l, r]$ 上的所有值都加上一个 $val$，在原序列上要操作 $r-l+1$ 次（对应每个位置都加一次），而在差分序列上只需要操作 2 次（只需要 $b[l] + val, b[r+1] - val$）即可。

如果这种区间操作需要很多次，最后的查询只有一次的话，就非常适合在差分序列上操作。

区间加法

假设你有一个长度为 n 的数组，初始情况下所有的数字均为 0，你将会被给出 k 个更新的操作。

其中，每个操作会被表示为一个三元组：[startIndex, endIndex, inc]，你需要将子数组 A[startIndex ... endIndex]（包括 startIndex 和 endIndex）增加 inc。

请你返回 k 次操作后的数组。

利用上面的差分性质这道题很容易解决，否则就要不停的遍历区间去加。

class Solution {
public:
    vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {
        vector<int> ans(length, 0);
        vector<int> chafen(length, 0);
        for(auto u : updates)
        {
            chafen[u[0]] += u[2];
            if(u[1] + 1 < length) chafen[u[1]+1] -= u[2];
        }
        for(int i = 0; i < length; i++)
        {
            if(i == 0) ans[i] = chafen[i];
            else ans[i] = ans[i-1] + chafen[i];
        }
        return ans;
    }
};

上面的代码还可以进一步优化，直接把 ans 数组当成差分数组。

class Solution {
public:
    vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {
        vector<int> ans(length, 0);
        for(auto u : updates)
        {
            ans[u[0]] += u[2];
            if(u[1] + 1 < length) ans[u[1]+1] -= u[2];
        }
        for(int i = 1; i < length; i++)
        {
            ans[i] += ans[i-1];
        }
        return ans;
    }
};