算法数据结构

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

字数统计: 1.7k字   |   阅读时长: 7分
,

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

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的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