前缀和题型总结 I： leetcode 467、795、904、992、1109

一般处理的时候要求连续，或者求连续子序列等问题都可以想一下前缀和是否可以解决

leetcode 467：环绕字符串中唯一的子字符串

题目描述：
把字符串 s 看作 “abcdefghijklmnopqrstuvwxyz” 的无限环绕字符串，所以 s 看起来是这样的：“…zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd…” 。现在给定另一个字符串 p 。返回 s 中 不同 的 p 的 非空子串 的数量 。
示例1：
输入：p = “a”
输出：1
解释：字符串 s 中只有 p 的一个 “a” 子字符。

示例 2：
输入：p = “cac”
输出：2
解释：字符串 s 中只有 p 的两个子串 (“a”, “c”) 。

示例 3：
输入：p = “zab”
输出：6
解释：在字符串 s 中有 p 的六个子串 (“z”, “a”, “b”, “za”, “ab”, “zab”) 。

提示：
1 <= p.length <= 10^5
p 由小写英文字母组成

思路1： 动态规划DP

class Solution:
    def findSubstringInWraproundString(self, p: str) -> int:
        # 定义状态为 以i结尾的字符串的数量
        dp = [0 for _ in range(len(p))]
        dp[0] = 1
        map = {}
        map[p[0]] = 1
        self.res = 0
        for i in range(1, len(p)):
            if self.close(p[i-1], p[i]):
                dp[i] = 1 + dp[i-1]
            else:
                dp[i] = 1
            if p[i] in map:
                if map[p[i]] < dp[i]:
                    map[p[i]] = dp[i]
            else:
                map[p[i]] = dp[i]
        for key in map:
            self.res += map[key]
        return self.res

    def close(self, x, y):
        if ord(y) - ord(x) == 1:
            return True
        if x == 'z' and y == 'a':
            return True
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

这里需要注意使用一个map进行了去重处理，比如"cac"示例，c不能被计算成为两个。
思路2： 前缀和
由题干即求连续子字符串的数量，只不过在连续的时候需要保证是字母挨着的满足要求，可以由笔记上的母题推的本题利用前缀和解决的方式：

class Solution:
    def findSubstringInWraproundString(self, p: str) -> int:
        dict_char = dict()
        pre = 1
        dict_char[p[0]] = pre
        for i in range(1, len(p)):
            if ord(p[i]) - ord(p[i-1]) == 1 or ord(p[i])-ord(p[i-1]) == -25:
                pre += 1
            else:
                pre = 1
            if p[i] in dict_char:
                dict_char[p[i]] = max(dict_char.get(p[i]), pre)
            else:
                dict_char[p[i]] = pre
        ans = 0
        for k in dict_char:
            ans += dict_char[k]
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

对于这类的前缀和，需要注意的就是pre的求取，正常只是求连续的子序列的话就是：

pre += 1
ans += pre
1
2

有特殊需求的时候，对pre要进行一些处理。

leetcode 795：区间子数组个数

题目描述：
给你一个整数数组 nums 和两个整数：left 及 right 。找出 nums 中连续、非空且其中最大元素在范围 [left, right] 内的子数组，并返回满足条件的子数组的个数。
生成的测试用例保证结果符合 32-bit 整数范围。

示例 1：
输入：nums = [2,1,4,3], left = 2, right = 3
输出：3
解释：满足条件的三个子数组：[2], [2, 1], [3]

示例 2：
输入：nums = [2,9,2,5,6], left = 2, right = 8
输出：7

提示：
1 <= nums.length <= 105
0 <= nums[i] <= 109
0 <= left <= right <= 109

思路： 前缀和
和前缀和的母题其中一个很相似，就是求not greater[right] 和 not greater[left-1]之间的差就是满足要求的连续子序列。

class Solution:
    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:
        def notgreater(k):
            pre, ans = 0, 0
            for i in range(len(nums)):
                if nums[i] <= k:
                    pre += 1
                else:
                    pre = 0
                ans += pre
            return ans
        
        return notgreater(right)-notgreater(left-1)
1
2
3
4
5
6
7
8
9
10
11
12
13

leetcode 904： 水果成篮

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。
你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：
你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。

示例 1：
输入：fruits = [1,2,1]
输出：3
解释：可以采摘全部 3 棵树。

示例 2：
输入：fruits = [0,1,2,2]
输出：3
解释：可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。

示例 3：
输入：fruits = [1,2,3,2,2]
输出：4
解释：可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。

示例 4：
输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：可以采摘 [1,2,1,1,2] 这五棵树。

提示：
1 <= fruits.length <= 10^5
0 <= fruits[i] < fruits.length

思路： 前缀和
本题的意思即是求在数组中连续的两个不同数出现的总次数和。
因为要连续所以想到尝试利用前缀和解决。
遍历一遍数组输出最长的只有两种元素的区间，从头开始往后走，记录已经收集的元素种类，一旦超过两个，前面的指针向后移动直到恢复到两个为止。

class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        k, ans = 2, 0
        dict_fruit = dict()
        i, j = 0, 0
        for j in range(len(fruits)):
            if fruits[j] not in dict_fruit or dict_fruit[fruits[j]] == 0:
                dict_fruit[fruits[j]] = 0
                k -= 1
            dict_fruit[fruits[j]] += 1
            while k < 0:
                dict_fruit[fruits[i]] -= 1
                if dict_fruit[fruits[i]] == 0:
                    k += 1
                i += 1
            ans = max(ans, j-i+1)
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

leetcode 992：K个不同整数的子数组

题目描述：
给定一个正整数数组 nums和一个整数 k ，返回 num 中 「好子数组」 的数目。

如果 nums 的某个子数组中不同整数的个数恰好为 k，则称 nums 的这个**连续、**不一定不同的子数组为 「好子数组 」。

例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。
子数组 是数组的 连续 部分。

示例 1：
输入：nums = [1,2,1,2,3], k = 2
输出：7
解释：恰好由 2 个不同整数组成的子数组：[1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].

示例 2：
输入：nums = [1,2,1,3,4], k = 3
输出：3
解释：恰好由 3 个不同整数组成的子数组：[1,2,1,3], [2,1,3], [1,3,4].

提示：
1 <= nums.length <= 2 * 104
1 <= nums[i], k <= nums.length

思路： 前缀和
这题和上一套水果的问题是很相似的，只不过是要求数量为k，并且所求是子数组的数量，不是长度；因为题目中提到了是要连续的要求，而且是求子序列的个数，所以想到了用前缀和；因为要求恰好是K个不同数的子序列数量，可以转换为求not greater(k) - not greater(k-1)。

class Solution:
    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:
        def atMost(k):
            ans, i, pre = 0, 0, 0
            dict_num = dict()
            for j in range(len(nums)):
                if nums[j] not in dict_num or dict_num[nums[j]] == 0:
                    k -= 1
                    dict_num[nums[j]] = 0
                dict_num[nums[j]] += 1
                while k < 0:
                    dict_num[nums[i]] -= 1
                    if dict_num[nums[i]] == 0:
                        k += 1
                    i += 1
                ans += j - i + 1  # 注意这里的计算方式，相当于在以i开头的数组求连续子序列时以j结尾的子序列个数
            return ans

        return atMost(k)-atMost(k-1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

leetcode 1109：航班预计统计

题目描述：
这里有 n 个航班，它们分别从 1 到 n 进行编号。
有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [first_i, last_i, seats_i] 意味着在从 first_i 到 last_i （包含 first_i 和 last_i ）的 每个航班 上预订了 seats_i 个座位。

请你返回一个长度为 n 的数组 answer，里面的元素是每个航班预定的座位总数。

示例 1：
输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
输出：[10,55,45,25,25]
解释：
航班编号 1 2 3 4 5
预订记录 1 ： 10 10
预订记录 2 ： 20 20
预订记录 3 ： 25 25 25 25
总座位数： 10 55 45 25 25
因此，answer = [10,55,45,25,25]

示例 2：
输入：bookings = [[1,2,10],[2,2,15]], n = 2
输出：[10,25]
解释：
航班编号 1 2
预订记录 1 ： 10 10
预订记录 2 ： 15
总座位数： 10 25
因此，answer = [10,25]

提示：
1 <= n <= 2 * 10^4
1 <= bookings.length <= 2 * 10^4
bookings[i].length == 3
1 <= first_i <= last_i <= n
1 <= seatsi <= 10^4

思路： 前缀和
[i, j, k] 其实代表的是 第 i 站上来了 k 个⼈， ⼀直到 第 j 站都在⻜机上，
到第 j + 1 就不在⻜机上了。所以第 i 站到第 j 站的每⼀站都会因此多 k 个
⼈。
因为题目中数组长度的限制，需要保证在O(n)的时间复杂度完成任务；考虑到相当于在i后的每个数都要加k，但是是到 j 为止，所以可以理解为 j 后面需要在加上 k 之后再减去k；所以一个做法就是利用前缀和，在i处值为k，j + 1处为-k；这样所求就是当前位置的前缀和，即一共在当前位置上来了多少个人。

class Solution:
    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
        count = [0] * n
        for i, j, k in bookings:
            count[i-1] += k
            if j < n:
                count[j] -= k
        for a in range(1, n):
            count[a] += count[a-1]
        return count
1
2
3
4
5
6
7
8
9
10

理解成上下车会容易理解一点，画一个示意图就能更好的理解解法。