算法解析：前缀和

Question

从力扣中精选了五道相同思想的题目，来帮助大家解套：

• 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[