基本概念和简单实用
滑动窗口和前缀和在连续问题中，对于优化时间复杂度有着很重要的意义。 因此如果一道题你可以用暴力解决出来，而且题目恰好有连续的限制， 那么滑动窗口和前缀和等技巧就应该被想到。
有 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[𝑖]得到每一位前缀和的值，从而通过前缀和进行相应的计算和解题。如果想得到某一个连续区间[l,r]的和则可以通过 pre[r] - pre[l-1] 取得，不过这里 l 需要 > 0。我们可以加一个特殊判断，如果 l = 0，区间 [l,r] 的和就是 pre[r]。
如果让你求一个数组的连续子数组总个数，你会如何求？其中连续指的是数组的索引连续。 比如 [1,3,4]，其连续子数组有：[1], [3], [4], [1,3], [3,4] , [1,3,4]，你需要返回 6。
一种思路是总的连续子数组个数等于：以索引为 0 结尾的子数组个数 + 以索引为 1 结尾的子数组个数 + … + 以索引为 n - 1 结尾的子数组个数，这无疑是完备的。
def countSubArray(nums):
ans = 0
pre = 0
for _ in nums:
pre += 1
ans += pre
return ans
而由于以索引为 i 结尾的子数组个数就是 i + 1，因此这道题可以直接用等差数列求和公式 (1 + n) * n / 2，其中 n 数组长度。
继续修改下题目， 如果让你求一个数组相邻差为 1 连续子数组的总个数呢？（如果只有一个数，那么我们也认为其实一个相邻差为 1 连续子数组）其实就是索引差 1 的同时，值也差 1。
def countSubArray(nums):
ans = 1
pre = 1
for i in range(1,len(nums)):
if nums[i]-nums[i-1]==1:
pre+=1
else:
pre=1
ans+=pre
return ans
如果我值差只要大于 1 就行呢？其实改下符号就行了，这不就是求上升子序列个数么？这里不再继续赘述， 大家可以自己试试。
我们继续扩展。
如果我让你求出不大于 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)。
def atMostK(k,nums):
ans = 0
pre = 0
for i in range(len(nums)):
if nums[i]<=k:
pre+=1
else:
pre=0
ans+=pre
return ans
如果我让你求出子数组最大值刚好是 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)。
如果我让你求出子数组最大值刚好是 介于 k1 和 k2 的子数组的个数呢？实现函数 betweenK(k1, k2, nums)。
实际上是 betweenK 可以直接利用 atMostK，即 atMostK(k1, nums) - atMostK(k2 - 1, nums)，其中 k1 > k2。前提是值是离散的， 比如上面我出的题都是整数。 因此我可以直接 减 1，因为 1 是两个整数最小的间隔。因此 atMostK 就是灵魂方法。
应用场景
上面是前缀和的基本概念以及简单使用。这里，我们总结一下前缀和的常见使用场景。大家碰到类似场景，不妨思考一下是否可通过前缀和以空间换时间的方式解决。
- 差分（后面我们要讲的 1109. 航班预订统计 就使用了这个技巧）
前缀和与二分。如果 nums 是一个正整数数组，那么其前缀和一定是单调递增的，有时候可以利用这个性质做二分。 - 求区间内的 1 的个数。比如给你一个数组 nums，让你求任意区间的 1 的个数。那么就可以先预处理，比如将 1 以外的数字预处理为 0，然后做前缀和，最后做差求区间和，这样区间和就是 1 的个数。（比如 1871. 跳跃游戏 VII 就利用了这个技巧）
- 区间值计数。上面是对 nums 区间本身进行统计。如果我想求 nums 的值（注意是值，不是索引）在 [lower,upper] 之间的数有多少，怎么求呢？我们可以开辟一个与 nums 值域大小等大的数组，并对值进行计数（即统计 nums 的值的出现频率），接下来就和普通前缀和一样了。（比如 1862. 向下取整数对和 就利用了这个技巧）
- 区间值计数扩展。上面的区间值计数没有对索引进行限制，那如果我加了索引的限制呢？比如我想求索引在 [l,r] 并且值在 [lower,upper]的值的个数如何求？我们可以先做一个二维前缀和 pre[i][j] 表示 前 i 项 j 的出现次数（显然 pre 的规模为数组长度乘以数组值域大小），接下来依次枚举 [lower,upper]的所有数 cur，并利用 pre[r][cur] - pre[l-1][cur]，将结果进行累加即可。（比如1906. 查询差绝对值的最小值 就使用了这个技巧）
有了上面的铺垫， 我们来看下第一道题。
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”。.
class Solution:
def findSubstringInWraproundString(self, p: str) -> int:
if not p:return 0
ans = 1
pre = 1
for i in range(1,len(p)):
if (ord(p[i])-ord(p[i-1]))%26==1:
pre+=1
else:
pre=1
ans+=pre
return ans
如上代码是有问题。 比如 cac会被计算为 3，实际上应该是 2。根本原因在于 c 被错误地计算了两次。因此一个简单的思路就是用 set 记录一下访问过的子字符串即可。
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]) % 26 ==1:
w += 1
else:
w = 1
len_mapper[p[i]] = max(len_mapper[p[i]], w)
return sum(len_mapper.values())
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]。
class Solution:
def numSubarrayBoundedMax(self, A: List[int], L: int, R: int) -> int:
return self.numSubarray(A,R)-self.numSubarray(A,L-1)
def numSubarray(self,A,R):
ans = 0
pre = 0
for i in range(len(A)):
if A[i]<=R:
pre+=1
else:
pre=0
ans+=pre
return ans
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
class Solution(object):
def totalFruit(self, tree):
"""
:type tree: List[int]
:rtype: int
"""
l=0
res=0
n=len(tree)
win=collections.defaultdict(lambda:0)
for r in range(n):
win[tree[r]]+=1
while len(win.keys())>2:
win[tree[l]]-=1
if win[tree[l]]==0:
win.pop(tree[l])
l+=1
res=max(res,r-l+1)
return res
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
class Solution(object):
def subarraysWithKDistinct(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
return self.subarraysWithK(nums,k)-self.subarraysWithK(nums,k-1)
def subarraysWithK(self,nums,k):
res=0
l=0
n=len(nums)
subarrays=collections.defaultdict(lambda:0)
for r in range(n):
subarrays[nums[r]]+=1
while len(subarrays)>k:
subarrays[nums[l]]-=1
if subarrays[nums[l]]==0:
subarrays.pop(nums[l])
l+=1
res+=r-l+1
return res
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
如上的代码复杂度太高，无法通过全部的测试用例。一种思路就是在 i 的位置 + k， 然后利用前缀和的技巧给 i 到 n 的元素都加上 k。但是题目需要加的是一个区间， j + 1 及其之后的元素会被多加一个 k。一个简单的技巧就是给 j + 1 的元素减去 k，这样正负就可以抵消。
class Solution(object):
def corpFlightBookings(self, bookings, n):
"""
:type bookings: List[List[int]]
:type n: int
:rtype: List[int]
"""
counter = [0] * n
for i,j,num in bookings:
counter[i-1] += num
if j<n: counter[j] -=num
for i in range(1,n):
counter[i] +=counter[i-1]
return counter
类似地，1004拼车如下：
There is a car with capacity empty seats. The vehicle only drives east (i.e., it cannot turn around and drive west).
You are given the integer capacity and an array trips where trip[i] = [numPassengersi, fromi, toi] indicates that the ith trip has numPassengersi passengers and the locations to pick them up and drop them off are fromi and toi respectively. The locations are given as the number of kilometers due east from the car’s initial location.
Return true if it is possible to pick up and drop off all passengers for all the given trips, or false otherwise.
class Solution(object):
def carPooling(self, trips, capacity):
"""
:type trips: List[List[int]]
:type capacity: int
:rtype: bool
"""
carpool=[0]*1001
for num,fr,to in trips:
carpool[fr]+=num
if carpool[fr]>capacity:return False
if to<1001:carpool[to]-=num
for i in range(1,1001):
carpool[i]+=carpool[i-1]
if carpool[i]>capacity:return False
return True
1871
给你一个下标从 0 开始的二进制字符串 s 和两个整数 minJump 和 maxJump 。一开始，你在下标 0 处，且该位置的值一定为 ‘0’ 。当同时满足如下条件时，你可以从下标 i 移动到下标 j 处：
i + minJump <= j <= min(i + maxJump, s.length - 1) 且
s[j] == ‘0’.
如果你可以到达 s 的下标 s.length - 1 处，请你返回 true ，否则返回 false 。
示例 1：
输入：s = “011010”, minJump = 2, maxJump = 3
输出：true
解释：
第一步，从下标 0 移动到下标 3 。
第二步，从下标 3 移动到下标 5 。
示例 2：
输入：s = “01101110”, minJump = 2, maxJump = 3
输出：false
提示：
2 <= s.length <= 105
s[i] 要么是 ‘0’ ，要么是 ‘1’
s[0] == ‘0’
1 <= minJump <= maxJump < s.length
class Solution(object):
def canReach(self, s, minJump, maxJump):
"""
:type s: str
:type minJump: int
:type maxJump: int
:rtype: bool
"""
n=len(s)
dp=[False]*n
dp[0]=True
if s[-1]=='1':return False
for j in range(minJump,n):
if s[j]=='0':
for jump in range(minJump,maxJump+1):
if dp[max(j-jump,0)]:
dp[j]=True
return dp[-1]
class Solution(object):
def canReach(self, s, minJump, maxJump):
"""
:type s: str
:type minJump: int
:type maxJump: int
:rtype: bool
"""
if s[-1]=='1':return False
n=len(s)
dp=[0]*n
dp[0]=1
pres=[0]*n
pres[0]=1
for j in range(1,n):
l=j-maxJump-1
r=j-minJump
dp[j]=s[j]=='0' and ((0 if r<0 else pres[r])-(0 if l<0 else pres[l]))>0
pres[j]=pres[j-1]+dp[j]
return dp[-1]
总结
这几道题都是滑动窗口和前缀和的思路。力扣类似的题目还真不少，大家只有多留心，就会发现这个套路。
前缀和的技巧以及滑动窗口的技巧都比较固定，且有模板可套。 难点就在于我怎么才能想到可以用这个技巧呢？
我这里总结了两点：
- 找关键字。比如题目中有连续，就应该条件反射想到滑动窗口和前缀和。比如题目求最大最小就想到动态规划和贪心等等。想到之后，就可以和题目信息对比快速排除错误的算法，找到可行解。这个思考的时间会随着你的题感增加而降低。
- 先写出暴力解，然后找暴力解的瓶颈， 根据瓶颈就很容易知道应该用什么数据结构和算法去优化。
最后推荐几道类似的题目， 供大家练习。
303. 区域和检索 - 数组不可变
1171. 从链表中删去总和值为零的连续节点
1186.删除一次得到子数组最大和
1310. 子数组异或查询
1371. 每个元音包含偶数次的最长子字符串
1402. 做菜顺序
|