【西法带你学算法】一次搞定前缀和

我花了几天时间，从力扣中精选了五道相同思想的题目，来帮助你们解套，若是以为文章对你有用，记得点赞分享，让我看到你的承认，有动力继续作下去。git

• 467. 环绕字符串中惟一的子字符串(中等)
• 795. 区间子数组个数(中等)
• 904. 水果成篮(中等)
• 992. K 个不一样整数的子数组（困难）
• 1109. 航班预订统计(中等)

前四道题都是滑动窗口的子类型，咱们知道滑动窗口适合在题目要求连续的状况下使用， 而前缀和也是如此。两者在连续问题中，对于优化时间复杂度有着很重要的意义。 所以若是一道题你能够用暴力解决出来，并且题目刚好有连续的限制， 那么滑动窗口和前缀和等技巧就应该被想到。github

除了这几道题， 还有不少题目都是相似的套路， 你们能够在学习过程当中进行体会。今天咱们就来一块儿学习一下。算法

前菜

咱们从一个简单的问题入手，识别一下这种题的基本形式和套路，为以后的四道题打基础。当你了解了这个套路以后， 以后作这种题就能够直接套。数组

须要注意的是这四道题的前置知识都是 滑动窗口， 不熟悉的同窗能够先看下我以前写的 滑动窗口专题（思路 + 模板）数据结构

母题 0

有 N 个的正整数放到数组 A 里，如今要求一个新的数组 B，新数组的第 i 个数 B[i]是原数组 A 第 0 到第 i 个数的和。app

这道题可使用前缀和来解决。 前缀和是一种重要的预处理，能大大下降查询的时间复杂度。咱们能够简单理解为“数列的前 n 项的和”。这个概念其实很容易理解，即一个数组中，第 n 位存储的是数组前 n 个数字的和。数据结构和算法

对 [1,2,3,4,5,6] 来讲，其前缀和能够是 pre=[1,3,6,10,15,21]。咱们可使用公式 pre[𝑖]=pre[𝑖−1]+nums[𝑖]获得每一位前缀和的值，从而经过前缀和进行相应的计算和解题。其实前缀和的概念很简单，但困难的是如何在题目中使用前缀和以及如何使用前缀和的关系来进行解题。ide

母题 1

若是让你求一个数组的连续子数组总个数，你会如何求？其中连续指的是数组的索引连续。 好比 [1,3,4]，其连续子数组有：[1], [3], [4], [1,3], [3,4] , [1,3,4]，你须要返回 6。函数

一种思路是总的连续子数组个数等于：以索引为 0 结尾的子数组个数 + 以索引为 1 结尾的子数组个数 + ... + 以索引为 n - 1 结尾的子数组个数，这无疑是完备的。学习

同时利用母题 0 的前缀和思路， 边遍历边求和。

参考代码(JS)：

function countSubArray(nums) {
  let ans = 0;
  let pre = 0;
  for (_ in nums) {
    pre += 1;
    ans += pre;
  }
  return ans;
}

复杂度分析

• 时间复杂度：$O(N)$，其中 N 为数组长度。
• 空间复杂度：$O(1)$

而因为以索引为 i 结尾的子数组个数就是 i + 1，所以这道题能够直接用等差数列求和公式 (1 + n) * n / 2，其中 n 数组长度。

母题 2

我继续修改下题目， 若是让你求一个数组相邻差为 1 连续子数组的总个数呢？其实就是索引差 1 的同时，值也差 1。

和上面思路相似，无非就是增长差值的判断。

参考代码(JS)：

function countSubArray(nums) {
  let ans = 1;
  let pre = 1;
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] - nums[i - 1] == 1) {
      pre += 1;
    } else {
      pre = 0;
    }

    ans += pre;
  }
  return ans;
}

复杂度分析

• 时间复杂度：$O(N)$，其中 N 为数组长度。
• 空间复杂度：$O(1)$

若是我值差只要大于 1 就行呢？其实改下符号就好了，这不就是求上升子序列个数么？这里再也不继续赘述， 你们能够本身试试。

母题 3

咱们继续扩展。

若是我让你求出不大于 k 的子数组的个数呢？不大于 k 指的是子数组的所有元素都不大于 k。 好比 [1,3,4] 子数组有 [1], [3], [4], [1,3], [3,4] , [1,3,4]，不大于 3 的子数组有 [1], [3], [1,3] ，那么 [1,3,4] 不大于 3 的子数组个数就是 3。 实现函数 atMostK(k, nums)。

参考代码（JS）:

function countSubArray(k, nums) {
  let ans = 0;
  let pre = 0;
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] <= k) {
      pre += 1;
    } else {
      pre = 0;
    }

    ans += pre;
  }
  return ans;
}

复杂度分析

• 时间复杂度：$O(N)$，其中 N 为数组长度。
• 空间复杂度：$O(1)$

母题 4

若是我让你求出子数组最大值恰好是 k 的子数组的个数呢？ 好比 [1,3,4] 子数组有 [1], [3], [4], [1,3], [3,4] , [1,3,4]，子数组最大值恰好是 3 的子数组有 [3], [1,3] ，那么 [1,3,4] 子数组最大值恰好是 3 的子数组个数就是 2。实现函数 exactK(k, nums)。

其实是 exactK 能够直接利用 atMostK，即 atMostK(k) - atMostK(k - 1)，缘由见下方母题 5 部分。

母题 5

若是我让你求出子数组最大值恰好是 介于 k1 和 k2 的子数组的个数呢？实现函数 betweenK(k1, k2, nums)。

其实是 betweenK 能够直接利用 atMostK，即 atMostK(k1, nums) - atMostK(k2 - 1, nums)，其中 k1 > k2。前提是值是离散的， 好比上面我出的题都是整数。 所以我能够直接 减 1，由于 1 是两个整数最小的间隔。

如上，小于等于 10 的区域减去 小于 5 的区域就是 大于等于 5 且小于等于 10 的区域。

注意我说的是小于 5， 不是小于等于 5。 因为整数是离散的，最小间隔是 1。所以小于 5 在这里就等价于 小于等于 4。这就是 betweenK(k1, k2, nums) = atMostK(k1) - atMostK(k2 - 1) 的缘由。

所以不难看出 exactK 其实就是 betweenK 的特殊形式。 当 k1 == k2 的时候， betweenK 等价于 exactK。

所以 atMostK 就是灵魂方法，必定要掌握，不明白建议多看几遍。

有了上面的铺垫， 咱们来看下第一道题。

467. 环绕字符串中惟一的子字符串（中等）

题目描述

把字符串 s 看做是“abcdefghijklmnopqrstuvwxyz”的无限环绕字符串，因此 s 看起来是这样的："...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....". 

如今咱们有了另外一个字符串 p 。你须要的是找出 s 中有多少个惟一的 p 的非空子串，尤为是当你的输入是字符串 p ，你须要输出字符串 s 中 p 的不一样的非空子串的数目。 

注意: p 仅由小写的英文字母组成，p 的大小可能超过 10000。

 

示例 1:

输入: "a"
输出: 1
解释: 字符串 S 中只有一个"a"子字符。
 

示例 2:

输入: "cac"
输出: 2
解释: 字符串 S 中的字符串“cac”只有两个子串“a”、“c”。.
 

示例 3:

输入: "zab"
输出: 6
解释: 在字符串 S 中有六个子串“z”、“a”、“b”、“za”、“ab”、“zab”。.
 

前置知识

• 滑动窗口

思路

题目是让咱们找 p 在 s 中出现的非空子串数目，而 s 是固定的一个无限循环字符串。因为 p 的数据范围是 10^5 ，所以暴力找出全部子串就须要 10^10 次操做了，应该会超时。并且题目不少信息都没用到，确定不对。

仔细看下题目发现，这不就是母题 2 的变种么？话很少说， 直接上代码，看看有多像。

为了减小判断， 我这里用了一个黑科技， p 前面加了个 ^。

class Solution:
    def findSubstringInWraproundString(self, p: str) -> int:
        p = '^' + p
        w = 1
        ans = 0
        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:
                w += 1
            else:
                w = 1
            ans += w
        return ans

如上代码是有问题。 好比 cac会被计算为 3，实际上应该是 2。根本缘由在于 c 被错误地计算了两次。所以一个简单的思路就是用 set 记录一下访问过的子字符串便可。好比：

{
    c,
    abc,
    ab,
    abcd
}

而因为 set 中的元素必定是连续的，所以上面的数据也能够用 hashmap 存：

{
    c: 3
    d: 4
    b: 1
}

含义是：

• 以 b 结尾的子串最大长度为 1，也就是 b。
• 以 c 结尾的子串最大长度为 3，也就是 abc。
• 以 d 结尾的子串最大长度为 4，也就是 abcd。

至于 c ，是没有必要存的。咱们能够经过母题 2 的方式算出来。

具体算法：

• 定义一个 len_mapper。key 是 字母， value 是 长度。 含义是以 key 结尾的最长连续子串的长度。

关键字是：最长

• 用一个变量 w 记录连续子串的长度，遍历过程根据 w 的值更新 len_mapper
• 返回 len_mapper 中全部 value 的和。

好比: abc，此时的 len_mapper 为:

{
    c: 3
    b: 2
    a: 1
}

再好比：abcab，此时的 len_mapper 依旧。

再好比: abcazabc，此时的 len_mapper：

{
    c: 4
    b: 3
    a: 2
    z: 1
}

这就获得了去重的目的。这种算法是不重不漏的，由于最长的连续子串必定是包含了比它短的连续子串，这个思想和 1297. 子串的最大出现次数 剪枝的方法有殊途同归之妙。

代码（Python）

class Solution:
    def findSubstringInWraproundString(self, p: str) -> int:
        p = '^' + p
        len_mapper = collections.defaultdict(lambda: 0)
        w = 1
        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:
                w += 1
            else:
                w = 1
            len_mapper[p[i]] = max(len_mapper[p[i]], w)
        return sum(len_mapper.values())

复杂度分析

• 时间复杂度：$O(N)$，其中 $N$ 为字符串 p 的长度。
• 空间复杂度：因为最多存储 26 个字母， 所以空间其实是常数，故空间复杂度为 $O(1)$。

795. 区间子数组个数（中等）

题目描述

给定一个元素都是正整数的数组 A ，正整数 L  以及  R (L <= R)。

求连续、非空且其中最大元素知足大于等于 L  小于等于 R 的子数组个数。

例如 :
输入:
A = [2, 1, 4, 3]
L = 2
R = 3
输出: 3
解释: 知足条件的子数组: [2], [2, 1], [3].
注意:

L, R  和  A[i] 都是整数，范围在  [0, 10^9]。
数组  A  的长度范围在[1, 50000]。

前置知识

• 滑动窗口

思路

由母题 5，咱们知道 betweenK 能够直接利用 atMostK，即 atMostK(k1) - atMostK(k2 - 1)，其中 k1 > k2。

由母题 2，咱们知道如何求知足必定条件（这里是元素都小于等于 R）子数组的个数。

这两个结合一下， 就能够解决。

代码（Python）

代码是否是很像

class Solution:
    def numSubarrayBoundedMax(self, A: List[int], L: int, R: int) -> int:
        def notGreater(R):
            ans = cnt = 0
            for a in A:
                if a <= R: cnt += 1
                else: cnt = 0
                ans += cnt
            return  ans

        return notGreater(R) - notGreater(L - 1)

复杂度分析

• 时间复杂度：$O(N)$，其中 $N$ 为数组长度。
• 空间复杂度：$O(1)$。

904. 水果成篮（中等）

题目描述

在一排树中，第 i 棵树产生 tree[i] 型的水果。
你能够从你选择的任何树开始，而后重复执行如下步骤：

把这棵树上的水果放进你的篮子里。若是你作不到，就停下来。
移动到当前树右侧的下一棵树。若是右边没有树，就停下来。
请注意，在选择一颗树后，你没有任何选择：你必须执行步骤 1，而后执行步骤 2，而后返回步骤 1，而后执行步骤 2，依此类推，直至中止。

你有两个篮子，每一个篮子能够携带任何数量的水果，但你但愿每一个篮子只携带一种类型的水果。

用这个程序你能收集的水果树的最大总量是多少？

 

示例 1：

输入：[1,2,1]
输出：3
解释：咱们能够收集 [1,2,1]。
示例 2：

输入：[0,1,2,2]
输出：3
解释：咱们能够收集 [1,2,2]
若是咱们从第一棵树开始，咱们将只能收集到 [0, 1]。
示例 3：

输入：[1,2,3,2,2]
输出：4
解释：咱们能够收集 [2,3,2,2]
若是咱们从第一棵树开始，咱们将只能收集到 [1, 2]。
示例 4：

输入：[3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：咱们能够收集 [1,2,1,1,2]
若是咱们从第一棵树或第八棵树开始，咱们将只能收集到 4 棵水果树。
 

提示：

1 <= tree.length <= 40000
0 <= tree[i] < tree.length

前置知识

• 滑动窗口

思路

题目花里胡哨的。咱们来抽象一下，就是给你一个数组， 让你选定一个子数组， 这个子数组最多只有两种数字，这个选定的子数组最大能够是多少。

这不就和母题 3 同样么？只不过 k 变成了固定值 2。另外因为题目要求整个窗口最多两种数字，咱们用哈希表存一下不就行了吗？

set 是不行了的。 所以咱们不但须要知道几个数字在窗口， 咱们还要知道每一个数字出现的次数，这样才可使用滑动窗口优化时间复杂度。

代码（Python）

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        def atMostK(k, nums):
            i = ans = 0
            win = defaultdict(lambda: 0)
            for j in range(len(nums)):
                if win[nums[j]] == 0: k -= 1
                win[nums[j]] += 1
                while k < 0:
                    win[nums[i]] -= 1
                    if win[nums[i]] == 0: k += 1
                    i += 1
                ans = max(ans, j - i + 1)
            return ans

        return atMostK(2, tree)

复杂度分析

• 时间复杂度：$O(N)$，其中 $N$ 为数组长度。
• 空间复杂度：$O(k)$。

992. K 个不一样整数的子数组（困难）

题目描述

给定一个正整数数组 A，若是 A 的某个子数组中不一样整数的个数刚好为 K，则称 A 的这个连续、不必定独立的子数组为好子数组。

（例如，[1,2,3,1,2] 中有 3 个不一样的整数：1，2，以及 3。）

返回 A 中好子数组的数目。

 

示例 1：

输入：A = [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：

输入：A = [1,2,1,3,4], K = 3
输出：3
解释：刚好由 3 个不一样整数组成的子数组：[1,2,1,3], [2,1,3], [1,3,4].
 

提示：

1 <= A.length <= 20000
1 <= A[i] <= A.length
1 <= K <= A.length

前置知识

• 滑动窗口

思路

由母题 5，知：exactK = atMostK(k) - atMostK(k - 1)， 所以答案便呼之欲出了。其余部分和上面的题目 904. 水果成篮 同样。

实际上和全部的滑动窗口题目都差很少。

代码（Python）

class Solution:
    def subarraysWithKDistinct(self, A, K):
        return self.atMostK(A, K) - self.atMostK(A, K - 1)

    def atMostK(self, A, K):
        counter = collections.Counter()
        res = i = 0
        for j in range(len(A)):
            if counter[A[j]] == 0:
                K -= 1
            counter[A[j]] += 1
            while K < 0:
                counter[A[i]] -= 1
                if counter[A[i]] == 0:
                    K += 1
                i += 1
            res += j - i + 1
        return res

复杂度分析

• 时间复杂度：$O(N)$，中 $N$ 为数组长度。
• 空间复杂度：$O(k)$。

1109. 航班预订统计（中等）

题目描述

这里有  n  个航班，它们分别从 1 到 n 进行编号。

咱们这儿有一份航班预订表，表中第  i  条预订记录  bookings[i] = [i, j, k]  意味着咱们在从  i  到  j  的每一个航班上预订了 k 个座位。

请你返回一个长度为 n 的数组  answer，按航班编号顺序返回每一个航班上预订的座位数。



示例：

输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
输出：[10,55,45,25,25]



提示：

1 <= bookings.length <= 20000
1 <= bookings[i][0] <= bookings[i][1] <= n <= 20000
1 <= bookings[i][2] <= 10000

前置知识

• 前缀和

思路

这道题的题目描述不是很清楚。我简单分析一下题目：

[i, j, k] 其实表明的是 第 i 站上来了 k 我的， 一直到 第 j 站都在飞机上，到第 j + 1 就不在飞机上了。因此第 i 站到第 j 站的每一站都会所以多 k 我的。

理解了题目只会不难写出下面的代码。

class Solution:
    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
        counter = [0] * n

        for i, j, k in bookings:
            while i <= j:
                counter[i - 1] += k
                i += 1
        return counter

如上的代码复杂度过高，没法经过所有的测试用例。

注意到里层的 while 循环是连续的数组所有加上一个数字，不难想到能够利用母题 0 的前缀和思路优化。

一种思路就是在 i 的位置 + k， 而后利用前缀和的技巧给 i 到 n 的元素都加上 k。可是题目须要加的是一个区间， j + 1 及其以后的元素会被多加一个 k。一个简单的技巧就是给 j + 1 的元素减去 k，这样正负就能够抵消。

代码（Python）

class Solution:
    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
        counter = [0] * (n + 1)

        for i, j, k in bookings:
            counter[i - 1] += k
            if j < n: counter[j] -= k
        for i in range(n + 1):
            counter[i] += counter[i - 1]
        return counter[:-1]

复杂度分析

• 时间复杂度：$O(N)$，中 $N$ 为数组长度。
• 空间复杂度：$O(N)$。

总结

这几道题都是滑动窗口和前缀和的思路。力扣相似的题目还真很多，你们只有多留心，就会发现这个套路。

前缀和的技巧以及滑动窗口的技巧都比较固定，且有模板可套。 难点就在于我怎么才能想到能够用这个技巧呢？

我这里总结了两点：

1. 找关键字。好比题目中有连续，就应该条件反射想到滑动窗口和前缀和。好比题目求最大最小就想到动态规划和贪心等等。想到以后，就能够和题目信息对比快速排除错误的算法，找到可行解。这个思考的时间会随着你的题感增长而下降。
2. 先写出暴力解，而后找暴力解的瓶颈， 根据瓶颈就很容易知道应该用什么数据结构和算法去优化。

最后推荐几道相似的题目， 供你们练习，必定要本身写出来才行哦。

• 303. 区域和检索 - 数组不可变
• 1186.删除一次获得子数组最大和
• 1310. 子数组异或查询
• 1371. 每一个元音包含偶数次的最长子字符串

你们对此有何见解，欢迎给我留言，我有时间都会一一查看回答。

更多算法套路能够访问个人 LeetCode 题解仓库：https://github.com/azl3979858... 。 目前已经 36K star 啦。

你们也能够关注个人公众号《力扣加加》带你啃下算法这块硬骨头。