文档教程知识库【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址https://gitcode.com/gh_mirrors/le/leetcode点击查看免费下载导读本文是 leetcode 题解仓库中「前缀和专题」thinkings/prefix.md的深度展开。专题以连续这一关键字为线索先用五个递进的母题建立前缀和 滑动窗口的统一解题套路再以 467、795、904、992、1109 五道 LeetCode 原题验证套路。读完本文你将掌握 atMostK 这个灵魂方法、exactK / betweenK 的容斥变形以及前缀和差分区间加法的实战用法并能把同一套路迁移到仓库中 560、525、1310、1371 等一系列同类题目。为什么连续是这道题的题眼暴力解是绝大多数连续类题目的起点但题目一旦出现连续子数组连续子串的限制就应当条件反射般想到两类优化工具滑动窗口Sliding Window通过左右指针维护一段连续区间适合求解与区间内元素集合、计数、最值相关的子数组问题前缀和Prefix Sum通过预处理前 n 项之和把区间求和查询降为 O(1)适合与区间和、区间差分相关的子数组问题。二者都服务于同一个目标——优化时间复杂度。因此判断标准非常朴素能用暴力解出、且题目恰好带有连续限制就应该往滑动窗口和前缀和的方向思考。这与仓库中滑动窗口专题的结论一致求解连续子串 xxxx连续子数组 xxxx就应该可以想到滑动窗口。前菜五个母题搭建统一套路专题先用五个递进的母题建立识别套路的能力后续四道题全部是母题的变体。前置知识为滑动窗口模板与伪代码可参考仓库中的滑动窗口专题。母题 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[i] pre[i-1] nums[i]即可逐位求出。前缀和概念本身很简单难点在于如何在题目中识别并运用前缀和——这是整个专题真正的门槛。仓库中的 560. 和为 K 的子数组 就是前缀和的典型应用先用pre[j] - pre[i-1]表示任意区间[i, j]的和再配合哈希表统计pre[j] - k出现次数即可在 O(N) 内完成计数。入门练习题可做 1480. 一维数组的动态和。母题 1连续子数组的总个数求一个数组连续子数组的总个数连续指索引连续。如[1,3,4]的连续子数组有[1], [3], [4], [1,3], [3,4], [1,3,4]返回 6。一种完备的思路是总数 以索引 0 结尾的子数组个数 以索引 1 结尾的子数组个数 ... 以索引 n-1 结尾的子数组个数。同时利用母题 0 的边遍历边累加思路参考代码JSfunction countSubArray(nums) { let ans 0; let pre 0; for (_ in nums) { pre 1; ans pre; } return ans; }复杂度分析时间复杂度 O(N)空间复杂度 O(1)。由于以索引 i 结尾的子数组个数就是 i1本题也可直接用等差数列求和公式(1 n) * n / 2n 为数组长度。这个以某个位置结尾计数的思路是整个专题的骨架。母题 2相邻差为 1 的连续子数组个数求一个数组相邻差为 1的连续子数组的总个数即索引差 1 的同时值也差 1。与母题 1 思路类似只是在遍历时增加对差值是否为 1 的判断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)空间复杂度 O(1)。若把差为 1改为差值大于等于 1只需改一下符号——这就变成求上升子序列个数了可作为课后练习自行验证。母题 3不大于 k 的子数组个数atMostK求所有元素都不大于 k 的子数组个数。如[1,3,4]不大于 3 的子数组有[1], [3], [1,3]个数为 3。实现函数atMostK(k, nums)。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)空间复杂度 O(1)。注意这里的计数技巧pre记录以当前位置结尾、且满足条件的最长连续段长度遇到不满足条件的元素就清零ans pre即等价于以当前位置结尾的合法子数组个数。这就是 atMostK 的灵魂。母题 4最大值刚好为 k 的子数组个数exactK求子数组最大值刚好是 k 的个数。如[1,3,4]中最大值刚好为 3 的子数组有[3], [1,3]个数为 2。实现exactK(k, nums)。exactK 可以直接利用 atMostK 推导exactK(k) atMostK(k) - atMostK(k - 1)原因在母题 5 中说明。母题 5最大值介于 k1 和 k2 之间的子数组个数betweenK求子数组最大值介于 k1 和 k2 之间的个数。实现betweenK(k1, k2, nums)。betweenK 同样由 atMostK 容斥得出betweenK(k1, k2, nums) atMostK(k1, nums) - atMostK(k2 - 1, nums)其中 k1 k2。其前提是值域离散例如题目中的整数此时可以直接减 1因为1 是两个整数间最小的间隔。直观理解小于等于 k1 的区域减去小于 k2 的区域得到的就是大于等于 k2 且小于等于 k1 的区域。注意是小于 k2而非小于等于 k2——由于整数离散、最小间隔为 1小于 k2 等价于小于等于 k2-1这正是atMostK(k2 - 1)的由来。由此可看出exactK 是 betweenK 的特殊形式当 k1 k2 时betweenK 退化为 exactK。因此atMostK 是整个专题的灵魂方法必须重点掌握。467. 环绕字符串中唯一的子字符串中等题目描述把字符串 s 看作是abcdefghijklmnopqrstuvwxyz的无限环绕字符串即...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....。给定另一个字符串 p求 s 中有多少个唯一的 p 的非空子串。p 仅由小写英文字母组成长度可能超过 10000。示例输入a输出 1s 中只有一个a输入cac输出 2s 中只有a、c两个子串输入zab输出 6z、a、b、za、ab、zab。前置知识滑动窗口思路s 是固定无限循环串p 的数据范围是 10^5暴力枚举所有子串需要约 10^10 次操作必然超时。仔细审题后发现这不就是母题 2 的变种么——求相邻字符在环绕串中连续差值为 1 或 -25的子串长度。为了减少边界判断可以在 p 前面加一个哨兵字符^。先看一个有问题的版本cac会被错误计算为 3实际应为 2根因是 c 被重复计算了两次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去重的朴素思路是用 set 记录访问过的子串。而由于 set 中元素一定是连续的可以用 hashmap 压缩存储key 为结尾字母value 为该字母结尾的最长连续子串长度例如{ c: 3 d: 4 b: 1 }含义是以 b 结尾的子串最大长度为 1即 b以 c 结尾的最大长度为 3即 abc以 d 结尾的最大长度为 4即 abcd。至于中间的 c 无需重复保存可通过母题 2 的方式推算出来。具体算法定义len_mapperkey 是字母value 是长度含义为以 key 结尾的最长连续子串的长度关键字最长用变量 w 记录当前连续子串长度遍历过程中按 w 更新len_mapper取 max返回len_mapper中所有 value 的和。该算法不重不漏因为最长的连续子串一定包含比它更短的连续子串——这一剪枝思想与仓库问题 1297. 子串的最大出现次数 的方法异曲同工。代码Pythonclass 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 和 RL R求连续、非空且最大元素满足大于等于 L、小于等于 R的子数组个数。示例A [2, 1, 4, 3]L 2R 3输出 3满足条件的子数组[2], [2, 1], [3]。注意L、R 和 A[i] 都是整数范围 [0, 10^9]数组长度范围 [1, 50000]。前置知识滑动窗口思路本题是母题 5 与母题 2 的直接组合由母题 5betweenK atMostK(k1) - atMostK(k2 - 1)k1 k2由母题 2已知如何求元素都满足某条件这里是小于等于 R的子数组个数。二者结合即可求解即notGreater(R) - notGreater(L - 1)。代码Pythonclass 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]输出 3可收集 [1,2,1]输入 [0,1,2,2]输出 3可收集 [1,2,2]从第一棵树开始只能收集 [0,1]输入 [1,2,3,2,2]输出 4可收集 [2,3,2,2]输入 [3,3,3,1,2,1,1,2,3,3,4]输出 5可收集 [1,2,1,1,2]。提示1 tree.length 400000 tree[i] tree.length。前置知识滑动窗口思路抽象题目给定数组选定一个最多只有两种数字的子数组求其最大长度。这不就是母题 3 的变形么——只是 k 变成了固定值 2。由于窗口内要求最多两种数字不能再使用 set而需要哈希表同时记录窗口内有哪些数字以及每个数字的出现次数这样才能在窗口收缩时正确维护计数从而用滑动窗口把时间复杂度优化到 O(N)。代码Pythonclass 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)这里 k 为常数 2实际为 O(1)。992. K 个不同整数的子数组困难题目描述给定正整数数组 A若 A 的某个子数组中不同整数的个数恰好为 K则称其为好子数组。返回 A 中好子数组的数目。示例A [1,2,1,2,3]K 2输出 7[1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2]A [1,2,1,3,4]K 3输出 3[1,2,1,3], [2,1,3], [1,3,4]。提示1 A.length 200001 A[i] A.length1 K A.length。前置知识滑动窗口思路由母题 5 直接可得exactK atMostK(k) - atMostK(k - 1)。于是答案呼之欲出其余部分与 904 题水果成篮几乎完全一致——事实上它与所有滑动窗口计数题目都同构。代码Pythonclass 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 200001 bookings[i][0] bookings[i][1] n 200001 bookings[i][2] 10000。前置知识前缀和思路题目描述较绕先分析语义[i, j, k]表示第 i 站上来 k 个人一直到第 j 站都在飞机上到第 j1 站就不在飞机上了。所以第 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但题目要求加的是一段区间[i, j]若直接前缀和j1 及其之后的元素会被多加一个 k于是再在 j1 位置 -k正负相抵前缀和后区间[i, j]恰好增加 k其余位置不变。这就是差分数组 前缀和区间增量问题的标准做法差分数组只需在两个端点打标记最终一次前缀和还原出每个位置的累加值。代码Pythonclass 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)。总结套路如何迁移到更多题目五道题贯穿同一条主线滑动窗口负责连续计数前缀和负责区间求和/区间增量两者套路固定、有模板可套。真正的难点在于如何想到用这个技巧。专题给出两点方法论找关键字题目出现连续就条件反射想到滑动窗口和前缀和题目求最大最小就想到动态规划和贪心。想到之后再与题目信息对比快速排除错误算法、锁定可行解——这种题感会随着刷题量增加而变强。先写暴力解再找瓶颈写出暴力解后分析瓶颈所在根据瓶颈自然推导出该用何种数据结构与算法优化。例如 1109 题暴力内层 while 是区间逐个加 k瓶颈在连续区间批量加于是自然引出差分前缀和。延伸练习仓库内配套题解下列仓库题目与本文套路同源建议独立完成303. 区域和检索 - 数组不可变——前缀和经典入门560. 和为 K 的子数组——前缀和 哈希表计数525. 连续数组——把 0/1 转为 -1/1前缀和求最长零和区间1310. 子数组异或查询——前缀异或异或的前缀和1371. 每个元音包含偶数次的最长子字符串——状态压缩 前缀和的进阶组合1186. 删除一次得到子数组最大和——连续子数组与动态规划的组合。更多滑动窗口题目与模板代码可继续阅读仓库的滑动窗口专题以及 209. 长度最小的子数组 等配套题解。赞分享文档教程知识库【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址https://gitcode.com/gh_mirrors/le/leetcode点击查看免费下载相关推荐LeetCode 前缀和与 atMostK 套路全解从母题推导到五道实战题一次搞定LeetCode 前缀和与 atMostK 套路全解从母题推导到五道实战题一次搞定 本文是 leetcode 题解仓库中「一次搞定前缀和」系列的技术解读对应文档教程知识库leetcode 题解仓库滑动窗口专题从双指针模板到 atMostK 进阶套路leetcode 题解仓库滑动窗口专题从双指针模板到 atMostK 进阶套路 本文是 leetcode 题解仓库中《滑动窗口Sliding Window文档教程知识库前缀和Prefix Sum / Cumulative Sum专题精讲从核心公式到 29 道 LeetCode 源码实战前缀和Prefix Sum / Cumulative Sum专题精讲从核心公式到 29 道 LeetCode 源码实战 导读 前缀和Cumulative示例工程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考