关于算法:西法带你学算法一次搞定前缀和

51次阅读

共计 8008 个字符，预计需要花费 21 分钟才能阅读完成。

我花了几天工夫，从力扣中精选了五道雷同思维的题目，来帮忙大家解套，如果感觉文章对你有用，记得点赞分享，让我看到你的认可，有能源持续做上来。

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

前四道题都是滑动窗口的子类型，咱们晓得滑动窗口适宜在题目要求间断的状况下应用，而前缀和也是如此。二者在间断问题中，对于 优化工夫复杂度 有着很重要的意义。因而如果一道题你能够用暴力解决进去，而且题目恰好有间断的限度，那么滑动窗口和前缀和等技巧就应该被想到。

除了这几道题，还有很多题目都是相似的套路，大家能够在学习过程中进行领会。明天咱们就来一起学习一下。

前菜

咱们从一个简略的问题动手，辨认一下这种题的根本模式和套路，为之后的四道题打基础。当你理解了这个套路之后，之后做这种题就能够间接套。

须要留神的是这四道题的前置常识都是 滑动窗口，不相熟的同学能够先看下我之前写的 滑动窗口专题（思路 + 模板）

母题 0

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

这道题能够应用前缀和来解决。前缀和是一种重要的预处理，能大大降低查问的工夫复杂度。咱们能够简略了解为“数列的前 n 项的和”。这个概念其实很容易了解，即一个数组中，第 n 位存储的是数组前 n 个数字的和。

对 [1,2,3,4,5,6] 来说，其前缀和能够是 pre=[1,3,6,10,15,21]。咱们能够应用公式 pre[????]=pre[????−1]+nums[????]失去每一位前缀和的值，从而通过前缀和进行相应的计算和解题。其实前缀和的概念很简略，但艰难的是如何在题目中应用前缀和以及如何应用前缀和的关系来进行解题。

母题 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 啦。

大家也能够关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

正文完
算法
发表至： 算法
2020-09-30
 0
关于算法:二叉树的序列化和反序列化
关于算法:广度优先搜索-深度优先搜索-动态规划-LeetCode题目传递信息
关于算法:R语言回测交易根据历史信号交易创建股票收益曲线
关于算法:ECON100-Macroeconomics探讨