前缀和 (差分)算法

什么是前缀和？前缀和是一个数组的某项下标之前(包括此项元素)的所有数组元素的和。

设 b[] 为前缀和数组，a[] 为原数组，根据这句话可以得到前缀和的定义式和递推式：

	定义式	递推式
一维前缀和	$b[i] = \sum_{j=0}^{i}a[j]$	$b[i] = b[i-1] + a[i]$
二维前缀和	$b[x][y] = \sum_{i=0}^{x}\sum_{j=0}^{y}a[i][j]$	$b[x][y] = b[x-1][y] + b[x][y-1] - b[x-1][y-1] + b[x][y]$

303. 区域和检索 - 数组不可变

题目描述：

给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。 

示例： 
给定 nums = [-2, 0, 3, -5, 2, -1]，求和函数为 sumRange()
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3 

说明: 
你可以假设数组不可变。 
会多次调用 sumRange 方法。 

Related Topics 动态规划

非常基础的前缀和算法，我们先计算并保存前缀和数组，检索的时候直接调用即可：

class NumArray:

    def __init__(self, nums):
        """
        :param nums: List[int]
        """
        self.nums = nums
        self.cumSums = [0]
        for num in self.nums:
            self.cumSums.append(self.cumSums[-1]+num)

    def sumRange(self, i: int, j: int) -> int:
        return self.cumSums[j+1] - self.cumSums[i]

304. 二维区域和检索 - 矩阵不可变

题目描述：

给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，
右下角为 (row2, col2)。 

上图子矩阵左上角 (row1, col1) = (2, 1) ，右下角(row2, col2) = (4, 3)，该子矩形内元素的总和为 8。 

示例: 
给定 matrix = [
  [3, 0, 1, 4, 2],
  [5, 6, 3, 2, 1],
  [1, 2, 0, 1, 5],
  [4, 1, 0, 1, 7],
  [1, 0, 3, 0, 5]
]

sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12

说明: 
你可以假设矩阵不可变。 
会多次调用 sumRegion 方法。 
你可以假设 row1 ≤ row2 且 col1 ≤ col2。 

Related Topics 动态规划

这又是非常基础的二维前缀和算法，我们先计算二维的前缀和数组并保存，检索的时候直接调用结果：

import numpy as np
class NumMatrix:

    def __init__(self, matrix):
        """
        前缀和
        :param matrix: List[List[int]]
        """
        self.matrix = np.array(matrix)
        if self.matrix.size == 0:
            return
        # 计算前缀和
        rows, cols = self.matrix.shape
        self.cumSums = np.zeros((rows+1, cols+1), dtype=int)
        for i in range(rows):
            for j in range(cols):
                self.cumSums[i+1, j+1] = self.cumSums[i, j+1] + self.cumSums[i+1, j] \
                                         - self.cumSums[i, j] + self.matrix[i, j]

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        return self.cumSums[row2+1, col2+1] - self.cumSums[row1, col2+1] - \
               self.cumSums[row2+1, col1] + self.cumSums[row1, col1]

525. 连续数组

题目描述：

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

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

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

注意: 给定的二进制数组的长度不会超过50000。 
Related Topics 哈希表

首先想到的是暴力解法，遍历每个子区间，统计 0 和 1 的数量，如果 0 和 1 的数量相等，再更新最大长度，这样的时间复杂度为 $O(n^3)$ ；我们可以在这个基础上进行优化，在外层循环内定义两个变量 zeros 和 ones 来记录 0 和 1 的数量，这样可以将时间复杂度降低至 $O(n^2)$ 。

class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        if nums is None or len(nums) <= 1:
            return 0
        maxlen = 0
        for i in range(len(nums)):
            zeros, ones = 0, 0
            for j in range(i, len(nums)):
                if nums[j] == 0:
                    zeros += 1
                else:
                    ones += 1
                if zeros == ones:
                    maxlen = max(maxlen, j-i+1)
        return maxlen

当我们欣喜的点击提交后，缺迟迟未得到反馈结果，终于：超出时间限制。
想想 $O(n^2)$ 的时间复杂度，确实不够高效。那又该从何开始优化呢？

仔细分析上面的解法，如上图，我们要求的子区间为，为整个区间的起点，为要求的子区间的起点，为要求的子区间的终点。我们依次固定点，然后遍历、计数、判断、更新结果。由于在之间，我们每次循环都要重复遍历一遍的某个子区间，那有没有办法通过一次遍历就得到结果呢？一次遍历，那肯定需要记录多个结果，所以肯定要用到哈希表。我们再来看哈希表记录什么，由于子区间中 0 和 1 数量相等，假如我们将 0 改为 -1，那区间之间 0(-1) 和 1 求和恰好为 0，也就是说之间 0(-1) 和 1 求和的结果和之间 0(-1) 和 1 求和的结果是相同的！也就是说当我们遇到两个相同求和结果的时候，便是满足 0 和 1 相等的时候，此时的区间也就是满足条件的一个候选区间，那该如何计算区间的长度呢？我们只需要知道上一次该求和结果的位置。所以哈希表需要记录的数据便也清楚了：求和结果为键，上一次的位置为值。
但是仔细一思考发现，题目要求的是最长的子区间，所以我们哈希表记录的值应该为求和结果第一次出现的位置。

class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        if nums is None or len(nums) <= 1:
            return 0
        maxlen, count = 0, 0
        # 记录该count下的第一个index
        hashmap = {0: -1}
        for i in range(len(nums)):
            count += 1 if nums[i] == 0 else -1
            if hashmap.get(count) is not None:
                maxlen = max(maxlen, i-hashmap.get(count))
            else:
                hashmap[count] = i
        return maxlen

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 只包含小写英文字母。 
Related Topics 字符串

题目分析：
要求最长子字符串，也就是一个最长子区间，那和我们上一题类似。在上一题中，我们的 count 变量是记录 0 比 1 多出来的次数，当区间 0 和 1 次数相等时，count 变量还是同一个值。类比到此题，我们希望有一个变量能够记录元音字母 a, e, i, o, u 出现的次数，并且希望其在元音字母恰好出现了偶数次的时候，这个变量的值能够和上一次相等。
题目只是要求偶数次，偶数，即是 x % 2 == 0，那我们便可以想到利用二进制来存储：当出现一次(奇数次)时，我们记录为 1，出现两次(偶数次)时，我们记录为 0，于是可以利用异或 ^ 来计算结果。由于要记录5个元音字母，那我们可以用5个二进制位来进行记录，所以这里的 count 范围为 00000-11111。当区间中元音字母都出现偶数次时，count 还是同一个结果。(代码中的 status 即为分析中的 count)

class Solution:
    def findTheLongestSubstring(self, s: str) -> int:
        # status 用来记录元音字母出现的奇偶性组合
        maxlen, status = 0, 0
        # 记录status第一次出现的位置
        hashmap = {0: -1}
        for i in range(len(s)):
            if s[i] == 'a':
                status ^= 1 << 0
            elif s[i] == 'e':
                status ^= 1 << 1
            elif s[i] == 'i':
                status ^= 1 << 2
            elif s[i] == 'o':
                status ^= 1 << 3
            elif s[i] == 'u':
                status ^= 1 << 4
            if hashmap.get(status) is not None:
                maxlen = max(maxlen, i-hashmap.get(status))
            else:
                hashmap[status] = i
        return maxlen