Leetcode上面关于前缀和+哈希的系列题目

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

注意:
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，且长度最长。
进阶:
你能使时间复杂度在 O(n) 内完成此题吗?

• 分析：本题需要寻找一个子数组的区间和等于k,对于区间和最简单的求法就是利用前缀和数组。对于区间i-j可以通过Sum[j+1]-Sum[i]来求。所以我们可以把问题转化为,在j之间的前缀和中,有没有那个Sum[i]=Sum[j+1]-k,若存在,则j-i就是一个符合条件的区间。为了方便查找，利用哈希结构来存储前缀和对应的索引。

  class Solution:
    def maxSubArrayLen(self, nums: List[int], k: int) -> int:
        Sum = 0
        res = 0
        hashMap = {0:-1}
        for i in range(len(nums)):
            Sum += nums[i]
            if Sum-k in hashMap:
                res = max(res, i-hashMap[Sum-k])
            if Sum not in hashMap:
                hashMap[Sum] = i
        return res

523. 连续的子数组和
     给定一个包含 非负数 的数组和一个目标 整数 k，编写一个函数来判断该数组是否含有连续的子数组，其大小至少为 2，且总和为 k 的倍数，即总和为 n*k，其中 n 也是一个整数。

示例 1：

输入：[23,2,4,6,7], k = 6
输出：True
解释：[2,4] 是一个大小为 2 的子数组，并且和为 6。
示例 2：

输入：[23,2,6,4,7], k = 6
输出：True
解释：[23,2,6,4,7]是大小为 5 的子数组，并且和为 42。

说明：

数组的长度不会超过 10,000 。
你可以认为所有数字总和在 32 位有符号整数范围内。

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        Sum = 0
        hashMap = {0:-1}
        for i in range(len(nums)):
            Sum += nums[i]
            if k!=0:
                Sum = Sum%k
            if Sum in hashMap: #在i之前就出现过Sum 说明在i到hashMap[Sum]之间的数是刚好被k整除的
                if i-hashMap[Sum]>1:
                    return True
            else:
                hashMap[Sum] = i
        return False

525. 连续数组
     给定一个二进制数组, 找到含有相同数量的 0 和 1 的最长连续子数组（的长度）。

示例 1:

输入: [0,1]
输出: 2
说明: [0, 1] 是具有相同数量0和1的最长连续子数组。
示例 2:

输入: [0,1,0]
输出: 2
说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。

class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        n = len(nums)
        hashMap = {0:-1}
        res = 0
        Sum = 0
        for i in range(n):
            if nums[i]==0:
                Sum -= 1
            if nums[i]==1:
                Sum += 1
            if Sum in hashMap: #当出现相同的数,表示这两个数之间就是一个符合条件的子数组(累计和为0)
                res = max(res, i-hashMap[Sum])
            else:
                hashMap[Sum] = i
        return res

1371. 每个元音包含偶数次的最长子字符串
      给你一个字符串 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 <= s.length <= 5 x 10^5
s 只包含小写英文字母。

class Solution:
    def findTheLongestSubstring(self, s: str) -> int:
        hashMap = {(0, 0, 0, 0, 0):-1}
        Sum = [0, 0, 0, 0, 0]
        index = {'a':0, 'e':1, 'i':2, 'o':3, 'u':4}
        res = 0
        for i,c in enumerate(s):
            if c in ('a', 'e', 'i', 'o', 'u'):
                Sum[index[c]] = 0 if Sum[index[c]] else 1
            if tuple(Sum) in hashMap:
                res = max(res, i-hashMap[tuple(Sum)])
            if tuple(Sum) not in hashMap:
                hashMap[tuple(Sum)] = i
        return res