算法【构建前缀信息解决子数组问题】

本文需要对掌握哈希表的用法。

构建某个前缀信息比如最早出现、最晚出现、出现次数等，是很常见的技巧。除此之外，还有很多种类的前缀信息可以构建出来，解决很多子数组相关问题。下面通过几个题目加深对构建前缀信息这个方法的理解。

题目一

简要描述：构建前缀和数组。快速解决子数组范围求和的问题。

测试链接：https://leetcode.cn/problems/range-sum-query-immutable/

分析：通过构建前缀和数组，快速求解。代码如下。

class NumArray {
public:int prefix[10001];NumArray(vector<int>& nums) {prefix[0] = 0;for(int i = 1;i <= nums.size();++i){prefix[i] = prefix[i-1] + nums[i-1];}}int sumRange(int left, int right) {return prefix[right+1] - prefix[left];}
};/*** Your NumArray object will be instantiated and called as such:* NumArray* obj = new NumArray(nums);* int param_1 = obj->sumRange(left,right);*/

其中，prefix[i]代表0~i-1的累加和。

题目二

简要描述：构建前缀和最早出现的位置。返回无序数组中累加和为给定值的最长子数组长度。

测试链接：https://www.nowcoder.com/practice/36fb0fd3c656480c92b569258a1223d5

分析：通过上一个题目可以看出，这个题目也是构建前缀和。一个比较好想的思路，是以i位置结尾的前缀和从开头遍历找到最先符合prefix[i]-k的值的下标，这样就找到了以i位置结尾的最长符合条件的子数组。但这样一来，就会出现双重for循环，时间上大概率是过不去的。所以采用哈希表存储每个值最先出现的下标，当以i结尾的prefix[i]在哈希表中查到了所需要的值的下标，代表着可以计算出结果，如果没有查到代表不能计算出结果。然后查询prefix[i]是否在哈希表中，如果不在则如要将prefix[i]插入进哈希表。代码如下。

#include <iostream>
#include <map>
using namespace std;
int N, k;
int main() {int arr[100001];int ans = 0;int sum = 0;map<int, int> m;m.insert(make_pair(0, -1));cin>>N>>k;for(int i = 0;i < N;++i){cin>>arr[i];sum += arr[i];if(m.find(sum - k) != m.end()){ans = ans > (i-(*(m.find(sum - k))).second) ? ans : (i-(*(m.find(sum - k))).second);}if(m.count(sum) == 0){m.insert(make_pair(sum, i));}}cout<<ans<<endl;
}
// 64 位输出请用 printf("%lld")

其中，将0的下标设为-1是考虑到长度计算的方便。

题目三

简要描述：构建前缀和出现的次数。返回无序数组中累加和为给定值的子数组数量。

测试链接：https://leetcode.cn/problems/subarray-sum-equals-k/

分析：此题和题目二思路基本一致，只不过求得是数量。代码如下。

class Solution {
public:map <int, int> m;int subarraySum(vector<int>& nums, int k) {int ans = 0;int sum = 0;m.insert(make_pair(0, 1));for(int i = 0;i < nums.size();++i){sum += nums[i];if(m.find(sum - k) != m.end()){ans += (*(m.find(sum-k))).second;}if(m.count(sum) == 0){m.insert(make_pair(sum, 1));}else{((*(m.find(sum))).second)++;}}return ans;}
};

其中，map中key为前缀和，value为出现的次数。

题目四

简要描述：构建前缀和最早出现的位置。返回无序数组中正数和负数个数相等的最长子数组长度。

测试链接：https://www.nowcoder.com/practice/545544c060804eceaed0bb84fcd992fb

分析：此题和题目二差不多，将正数处理为1，负数处理为-1，k为0，就是题目二。代码如下。

#include <iostream>
#include <map>
using namespace std;
int N;
int main() {int arr[100001];int ans = 0;int sum = 0;map<int, int> m;m.insert(make_pair(0, -1));cin>>N;for(int i = 0;i < N;++i){cin>>arr[i];arr[i] = (arr[i] >= 0 ? (arr[i] > 0 ? 1 : 0) : -1);sum += arr[i];if(m.find(sum) != m.end()){ans = ans > (i-(*(m.find(sum))).second) ? ans : (i-(*(m.find(sum))).second);}if(m.count(sum) == 0){m.insert(make_pair(sum, i));}}cout<<ans<<endl;
}
// 64 位输出请用 printf("%lld")

题目五

简要描述：构建前缀和最早出现的位置。表现良好的最长时间段问题。

测试链接：https://leetcode.cn/problems/longest-well-performing-interval/

分析：此题和题目四差不多，将大于8处理为1，其余处理为-1，k设置为1。这里为什么设置k为1，是因为虽然子数组的和大于0都可以，但是一个子数组的和如果比1大，一定存在更长的具有相同下标结尾的和为1的子数组。比如下标i结尾的前缀和为x，假设找到了一个下标j（j < i）结尾的前缀和为x-2，那么就找到一个和为2的子数组，但是下标j之前一定存在前缀和为x-1的下标，因为要得到x-2，就必须经过x-1。所以只需将k设为1即可。代码如下。

class Solution
{
public:int longestWPI(vector<int> &hours){int ans = 0;int sum = 0;map<int, int> m;m.insert(make_pair(0, -1));for (int i = 0; i < hours.size(); ++i){sum += (hours[i] > 8 ? 1 : -1);if(sum > 0){ans = ans > (i+1) ? ans : (i+1);}else if (m.find(sum - 1) != m.end()){ans = ans > (i - (*(m.find(sum - 1))).second) ? ans : (i - (*(m.find(sum - 1))).second);}if (m.count(sum) == 0){m.insert(make_pair(sum, i));}}return ans;}
};

题目六

简要描述：构建前缀和余数最晚出现的位置。移除的最短子数组长度，使得剩余元素的累加和能被p整除。

测试链接：https://leetcode.cn/problems/make-sum-divisible-by-p/

分析：可以先求出整个数组和的总体余数，然后求出以下标i结尾的前缀和的余数，这两个余数之间的差值就是我们需要减掉子数组的余数，通过处理可以使差值一定为正。通过一个哈希表存储前缀和模p的余数的最后出现的下标位置，这样就可以求出每个下标结尾需要删除的子数组的长度，遍历数组得到最小值即可。代码如下。

class Solution {
public:int minSubarray(vector<int>& nums, int p) {int mod = 0;map <int, int> m;m.insert(make_pair(0, -1));for(int i = 0;i < nums.size();++i){mod = (mod + nums[i]) % p;}if(mod == 0){return 0;}int ans = nums.size();int cur = 0;int find;for(int i = 0;i < nums.size();++i){cur = (cur + nums[i]) % p;if(cur >= mod){find = cur - mod;}else{find = cur + p - mod;}if(m.count(find) != 0){cout<<(i - (*(m.find(find))).second)<<endl;ans = ans < (i - (*(m.find(find))).second) ? ans : (i - (*(m.find(find))).second);}m[cur] = i;}return ans == nums.size() ? -1 : ans;}
};

其中，cur为以下标i结尾的前缀和的余数，mod为整体余数，find为差值。

题目七

简要描述：构建前缀奇偶状态最早出现的位置。每个元音包含偶数次的最长子串长度。

测试链接：https://leetcode.cn/problems/find-the-longest-substring-containing-vowels-in-even-counts/

分析：通过五位来表示，aeiou数目是奇数还是偶数，偶数为0，奇数为1，所以总共需要32个数来表示，不再需要哈希表，而是直接申请一个数组。这个数组存储每个状态最先出现的下标，初始化为-2代表还没有出现这个状态。然后遍历字符串得到不同状态，如果这个状态存在最先出现下标，计算相邻两个相同状态之间的长度，这个长度就是以此下标结尾符合要求的子串长度。遍历字符串即可得到最长子串长度。代码如下。

class Solution {
public:int move(char ch){switch (ch){case 'a':/* code */return 0;break;case 'e':/* code */return 1;break;case 'i':/* code */return 2;break;case 'o':/* code */return 3;break;case 'u':/* code */return 4;break;default:return -1;break;}}int findTheLongestSubstring(string s) {vector<int> map;map.assign(32, -2);map[0] = -1;int ans = 0;for(int i = 0, status = 0;i < s.size();++i){int m = move(s[i]);if(m != -1){status ^= (1 << m);}if(map[status] == -2){map[status] = i;}else{ans = ans > (i - map[status]) ? ans : (i - map[status]);}}return ans;}
};

其中，move方法是确定哪一位变化，-1代表不变化。