每日一道算法之--前缀和总结

哈希表位运算前缀和状态压缩二进制

Word count: 2.2kReading time: 8 min

 2020/05/21   Share

前缀和总结

昨天刷到力扣每一一题第1371题《每个元音包含偶数次的最长子字符串》时，想了很久搜没有思路，于是我去看了题解，发觉这道题考察的知识点还挺多的，位运算，前缀和，哈希表的优化，状态压缩等，前缀和这一个知识点我尤其的好奇，因为我印象中就刷过两道，当时我记得那两道都不是用前缀和写的，也没去多在意，今天就好好总结一下前缀和这一东西.

1. 和为K的子数组

力扣第560题: https://leetcode-cn.com/problems/subarray-sum-equals-k/

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

示例 1 :

输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。

1.1 前缀和

参考作者：hyj8
链接：https://leetcode-cn.com/problems/subarray-sum-equals-k/solution/dai-ni-da-tong-qian-zhui-he-cong-zui-ben-fang-fa-y/

什么是前缀和：
- 从第 0 项到当前项的总和
如果用一个数组 prefixSum 表示：
prefixSum[x] = nums[0] + nums[1] +…+nums[x] (prefixSum[x]：nums 的第 0 到第 x 项的总和)

所以有，nums 某一项 = 两个相邻前缀和之差：
nums[x] = prefixSum[x] - prefixSum[x - 1]

所以有，nums 的第 i 到 j 项的总和：
nums[i] +…+nums[j]=prefixSum[j] - prefixSum[i - 1]

我们知道 i 当然可以为 0，此时 i - 1 为 - 1，我们让 prefixSum[-1] 为 0，此时：
nums[0] +…+nums[j]=prefixSum[j]

题目等价转化：

从【有几种 i、j 组合，使得从第 i 到 j 项的子数组的求和 === k】

↓ ↓ ↓ 转化为 ↓ ↓ ↓

【有几种 i、j 组合，满足 i < j 且 prefixSum[ j ] - prefixSum[ i - 1 ] === k】

于是我们想求出 prefixSum 数组的每一项，再看哪些项相减 === k，统计 count

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
      cnt, n =  0, len(nums)
      pre = [0] * (n + 1)
      for i in range(n):
          pre[i + 1] = pre[i] + nums[i]
      for i in range(n):
          for j in range(i, n):
              if (pre[j + 1] - pre[i] == k): cnt += 1
      return cnt

但通式有 i、j 2 个变量，需要两层 for 循环，时间复杂度依旧是 O(n^2)

前缀和 + 哈希表优化。

我们不关心前缀和具体对应哪一项，只关心前缀和的值和出现次数。
用 prefixSum 变量，保存当前项的前缀和，存入 map
这样 map 代替了 prefixSum 数组，记录出现过的前缀和和出现次数

核心流程

map 存什么键值对：
- 键：前缀和，从第 0 项到当前项的总和
- 值：这个前缀和值出现了几次
遍历 nums 之前，我们预置边界情况 (即之前提到的 prefixSum[-1] = 0)：map 初始放入 0:1 键值对，即预设已经出现 1 次为 0 的前缀和
遍历 nums 的每一项，求当前项的前缀和，存入 map 中
- 之前没有存过，则存入，初始值为 1
- 之前存过，则对应值 +1，即出现次数 +1
边存边查看 map ，如果 map 中已存在 key 为当前前缀和 - k
- 说明存在【之前求出的前缀和】，它的值满足【当前前缀和】-【之前求出的前缀和】 === k
- 把【之前求出的前缀和】出现的次数，累加给 count 计数器

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        count = 0
        nums_sum = 0
        res_has = {0:1}
        for num in nums:
            nums_sum += num
            if (nums_sum - k) in res_has :
               count += res_has[nums_sum - k]
            if nums_sum in res_has:
                res_has[nums_sum] += 1
            else:
                res_has[nums_sum] = 1
        return count

复杂度分析

时间复杂度：O(n)，其中 nn 为数组的长度。我们遍历数组的时间复杂度为 O(n)，中间利用哈希表查询删除的复杂度均为 O(1)，因此总时间复杂度为 O(n)。

空间复杂度：O(n)，其中 n 为数组的长度。哈希表在最坏情况下可能有 n 个不同的键值，因此需要 O(n) 的空间复杂度。

2. 统计「优美子数组」

力扣第1248题 : https://leetcode-cn.com/problems/count-number-of-nice-subarrays/
给你一个整数数组 nums 和一个整数 k。

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

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

示例 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

看了众多题解后,我慢慢开始理清了思路,看一下这道题,模板是一模一样的.

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        cnt = {0: 1}
        count = cur = 0
        for num in nums:
            if num % 2 != 0:
                cur += 1
            if (cur - k) in cnt:
                count += cnt[cur - k]
            if cur in cnt:
                cnt[cur] += 1
            else:
                cnt[cur] = 1
        return count

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

力扣第1371题: https://leetcode-cn.com/problems/find-the-longest-substring-containing-vowels-in-even-counts/

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

示例 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 次。

前缀和 + 状态压缩

1、状态压缩
这道题的状态压缩说实话我是没有想到的,其实感觉不难想到才对。

利用二进制和位运算，我们可以定义一个长度为5的二进制。00001表示出现了a，00010表示出现e，00100表示出现i，01000表示出现o，10000表示出现u，这样就会存在2^5即32种可能。
根据异或运算规律，异或本身为 0，根据这一点，可以判断出这个元音出现的次数是否为偶数。

2、前缀和

和上面两道题对比，可以发现，上面两道题我们是能明确知道两个前缀的差值是恒定的，而这道题的差值是变化的。
但是这个差值是为偶数，而且是个人都知道，如果两个数的奇偶性相同，那么他们的差值必为偶数。因此我们可以对前缀和稍作修改，从维护元音字母出现的次数改作维护元音字母出现次数的奇偶性
这样我们只要实时维护每个元音字母出现的奇偶性，可以利用哈希表存储每一种奇偶性（即考虑所有的元音字母）对应最早出现的位置，边遍历边更新答案。
因为用哈希表的话，维护起来比较浪费资源，利用上面的状态压缩，可以将状态用一个32长度的数组来存储。

class Solution:
    def findTheLongestSubstring(self, s: str) -> int:
        words = ['a', 'e', 'i', 'o', 'u']
        status, res = 0, 0
        pos = [0] + [-1] * 31
        for i, word in enumerate(s):
            if word in words:
                status ^= 1 << words.index(word)
        
            if pos[status] >= 0:
                res = max(res, i + 1 - pos[status])          
            else:
                pos[status] = i + 1
        return res