用数据结构维护前缀状态信息

  |  

摘要: 用前缀和的思想表示维护前缀上的状态信息

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


使用类似前缀和的处理方式,维护前缀或后缀的一些状态值,最常见的是维护前缀上各个元素值的计数信息,参考文章 用前缀和的思想快速计算区间上的指标(状态)

这些状态值同样可以用 HashMap 等数据结构维护,满足对状态值的出现次数、最早出现位置等信息的查询。本文通过三个题看一下用数据结构维护前缀上的信息的处理方法。


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

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

数据范围:

1
nums 数组的总和是一定在 32 位有符号整数范围之内的。

示例 1:
输入: nums = [1, -1, 5, -2, 3], k = 3
输出: 4
解释: 子数组 [1, -1, 5, -2] 和等于 3,且长度最长。
示例 2:
输入: nums = [-2, -1, 2, 1], k = 1
输出: 2
解释: 子数组 [-1, 2] 和等于 1,且长度最长。

算法: 前缀和+HashMap

顺序枚举数组的值,当前值为 nums[i], 计算当前的前缀和即当前状态 sums[i + 1] = sum[i] + nums[i]

若要以 nums[i] 为结尾的子数组的和为 k,则 sums[i + 1] - k 一定在之前出现过。

然后依据以上事实和当前状态更新答案: 记 sums[i + 1] - k 最早出现的位置为 start, 若没出现过则为 -1。

  • 若没出现过(start == -1): 将当前前缀和 sums[i] 以及位置 i 插入。
  • 若出现过(start >= 0): 则以 nums[i] 为结尾的和为 k 的子数组长度为 i - start,更新答案 result = max(result, i - start)

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
int maxSubArrayLen(vector<int>& nums, int k) {
if(nums.empty()) return 0;
int n = nums.size();
vector<int> sums(n + 1, 0);
unordered_map<int, int> mapping;
mapping.insert(pair<int, int>(0, 0)); // 前缀和的值 -> 对应前缀和数组的最左索引

int result = 0;
// nums[i..j] 的和 sums[j] - sums[i - 1]
for(int i = 1; i <= n; ++i)
{
sums[i] = sums[i - 1] + nums[i - 1];
int gap = sums[i] - k;
if(mapping.find(gap) != mapping.end())
result = max(result, i - mapping[gap]);
if(mapping.find(sums[i]) == mapping.end())
mapping.insert(pair<int, int>(sums[i], i));
}
return result;
}
};

1248. 统计「优美子数组」

给你一个整数数组 nums 和一个整数 k。

如果某个 连续 子数组中恰好有 k 个奇数数字,我们就认为这个子数组是「优美子数组」。

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

数据范围:

1
2
3
1 <= nums.length <= 50000
1 <= nums[i] <= 10^5
1 <= k <= nums.length

示例 1:
输入:nums = [1,1,2,1,1], k = 3
输出:2
解释:包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。
示例 2:
输入:nums = [2,4,6], k = 1
输出:0
解释:数列中不包含任何奇数,所以不存在优美子数组。
示例 3:
输入:nums = [2,2,2,1,2,2,1,2,2,2], k = 2
输出:16

算法: 频数前缀和+HashMap

维护前缀状态信息:前缀中奇数的个数。

顺序枚举数组的值,当前值为 nums[i], 计算当前的前缀状态 cur, cur 的含义是以 nums[i] 结尾的前缀中奇数的个数。

若以 nums[i] 结尾的子数组中存在有 k 个奇数的子数组,则 cur - k 这个状态此前必须出现过。

然后依据以上事实和当前状态更新答案: 记 cur - k 出现的次数为 x, result += x

更新当前状态出现的次数(+1)。

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int numberOfSubarrays(vector<int>& nums, int k) {
int n = nums.size();
vector<int> prefix_state(n + 1, 0);
prefix_state[0] = 1;
int odd_cnt = 0;
int result = 0;
for(int i = 0; i < n; ++i)
{
if(nums[i] & 1) ++odd_cnt;
if(odd_cnt - k >= 0)
result += prefix_state[odd_cnt - k];
++prefix_state[odd_cnt];
}
return result;
}
};

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

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

数据范围:

1
2
1 <= s.length <= 5 x 10^5
s 只包含小写英文字母。

示例 1:
输入:s = “eleetminicoworoep”
输出:13
解释:最长子字符串是 “leetminicowor” ,它包含 e,i,o 各 2 个,以及 0 个 a,u 。
示例 2:
输入:s = “leetcodeisgreat”
输出:5
解释:最长子字符串是 “leetc” ,其中包含 2 个 e 。
示例 3:
输入:s = “bcbcbc”
输出:6
解释:这个示例中,字符串 “bcbcbc” 本身就是最长的,因为所有的元音 a,e,i,o,u 都出现了 0 次。

算法: 频数前缀和+状态压缩+HashMap

前缀状态: 前缀中 a, e, i, o, u 的个数是奇数还是偶数,用一个位表示一个字母的奇偶状态,1 表示奇数,0 表示偶数。

可能的状态为 00000, 00001, …, 11111, 共 32 种。

顺序枚举数组的值,当前值为 s[i], 计算当前状态 cur_state:

  • s[i] 属于 a,e,i,o,u,则在上一个状态(状态压缩后的整数上翻转对应的位)
  • 否则 cur_state 等于上一个状态

若要以 s[i] 结尾的子串满足 a,e,i,o,u 均为偶数的条件,则 cur_state 状态此前必须出现过

例如,当前状态为 10100: 即以 s[i] 结尾的前缀中:a,i 为奇数个,e,o,u 为偶数个。需要有某个前缀的 a,i 也为奇数个,e,o,u 也为偶数个才行。

然后依据以上事实和当前状态更新答案: 记 cur_state 最早出现的位置为 start, result = max(result, i - start)

若当前状态未出现过 prefix_state[cur_state] == -1, 记录 prefix_state[cur_state] = i + 1

初始化 prefix_state[00000] == 0

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
int findTheLongestSubstring(string s) {
int n = s.size();
vector<int> prefix_state(1 << 5, -1); // 类似状态压缩的手法,用前 5 位表示 5 个元音字母的状态
prefix_state[0] = 0;
int result = 0;
int cur_state = 0;
for(int i = 0; i < n; ++i)
{
char c = s[i];
int idx = _id(c);
if(idx != -1)
cur_state ^= 1 << idx;
if(prefix_state[cur_state] == -1)
prefix_state[cur_state] = i + 1;
result = max(result, i + 1 - prefix_state[cur_state]);
}
return result;
}

private:
int _id(const char& ch)
{
switch(ch)
{
case('a'): return 0;
case('e'): return 1;
case('i'): return 2;
case('o'): return 3;
case('u'): return 4;
default: return -1;
}
}
};

Share