前缀和基础原理与题目说明

前缀和基础原理与题目说明

🔗 查看完整专栏（LeetCode基础算法专栏）

特别说明：

本文为个人的 LeetCode 刷题与学习笔记，内容仅供学习与交流使用，禁止转载或用于商业用途。需要强调的是，文中的题目解法不一定是最优解（可能存在时间或空间复杂度的进一步优化空间），主要目的是分享个人的解题思路与逻辑实现，仅供参考。笔记内容为个人理解与总结，可能存在疏漏或偏差，欢迎读者自行甄别并交流探讨。

一、 什么是前缀和（Prefix Sum）？

子数组定义：数组中元素的连续非空序列。

假设有数组nums = [1, 2, 3, 4]，我们定义：

p r e f i x [ i ] = n u m s [ 0 ] + n u m s [ 1 ] + . . . + n u m s [ i − 1 ] prefix[i] = nums[0] + nums[1] + ... + nums[i-1]prefix[i]=nums[0]+nums[1]+...+nums[i−1]

其中prefix就是前缀和数组，即prefix = [0, 1, 3, 6, 10]。（通常在前面补一个0方便计算）。

前缀和的核心用途：

它能以O ( 1 ) O(1)O(1)的时间复杂度快速求解任意连续子数组的和。

s u m ( i … j − 1 ) = p r e f i x [ j ] − p r e f i x [ i ] sum(i \dots j-1) = prefix[j] - prefix[i]sum(i…j−1)=prefix[j]−prefix[i]

二、 前缀和基础模板

构建完整prefix数组的代码骨架如下：

1. 初始化(为了处理从索引0开始的子数组，假定长度为n + 1 n+1n+1)

prefix=[0]*(n+1)

2. 构建前缀和数组

foriinrange(n):prefix[i+1]=prefix[i]+nums[i]

3. 计算子数组和

子数组nums[i ... j-1]的和即为：prefix[j] - prefix[i]。

三、 前缀和实战演练

前缀和算法很少单独出现，通常会结合哈希表（寻找特定差值）或树结构（DFS 路径上的前缀和）来解决更复杂的问题。

560. 和为K的子数组 (前缀和 + 哈希表)

题目描述：

给你一个整数数组nums和一个整数k，请你统计并返回该数组中和为k的连续子数组的个数。

解题思路：

如果单纯用双层循环枚举子数组，时间复杂度是O ( n 2 ) O(n^2)O(n2)。通过前缀和与哈希表可以优化到O ( n ) O(n)O(n)。

设i < j i < ji<j，如果nums[i]到nums[j-1]的元素和等于k，用前缀和表示即为：

p r e f i x [ j ] − p r e f i x [ i ] = k prefix[j] - prefix[i] = kprefix[j]−prefix[i]=k

移项可得：

p r e f i x [ i ] = p r e f i x [ j ] − k prefix[i] = prefix[j] - kprefix[i]=prefix[j]−k

因此，我们在遍历数组计算当前前缀和prefix[j]时，只需要用哈希表查找在此之前是否出现过prefix[j] - k这个值。

• 使用哈希表hashdict记录{前缀和: 出现次数}。
• 关键初始化：hashdict = Counter({0: 1})，这意味着前缀和为0的情况已经出现了一次，避免漏掉从数组最开头起始的有效子数组。

核心代码：

fromcollectionsimportCounterfromtypingimportListclassSolution:defsubarraySum(self,nums:List[int],k:int)->int:""" 前缀和 + 哈希表，一次 for 循环完成 """prefix=0hashdict=Counter({0:1})# prefix=0 默认已出现一次ans=0fornuminnums:# 1. 更新当前位置的前缀和prefix+=num# 2. 查询目标差值 (prefix - k) 是否在之前出现过ifprefix-kinhashdict:ans+=hashdict[prefix-k]# 3. 将当前前缀和存入哈希表，供后续位置查询hashdict[prefix]+=1returnans

53. 最大子数组和 (前缀和求极值)

题目描述：

给你一个整数数组nums，请你找出其中和最大的连续子数组（子数组至少包含一个元素），返回其和。

解题思路：

这是一道非常经典的题目，除了著名的贪心/动态规划解法外，用前缀和也能巧妙解决。

任意子数组的和可以表示为prefix - 之前出现过的某个前缀和。

要使这个子数组的和最大，我们必须减去一个最小的前缀和。

因此，遍历数组时，我们实时维护两个变量：

1. 当前的prefix。

2. 之前出现过的min_prefix（初始为0）。

   每次都用prefix - min_prefix去挑战全局最大和max_sum。

核心代码：

fromtypingimportListclassSolution:defmaxSubArray(self,nums:List[int])->int:# 前缀和方法prefix=0min_prefix=0# 遍历过程中最小的前缀和默认为0 (对应空前缀)max_sum=float('-inf')fornuminnums:prefix+=num# 当前前缀和 减去 历史最小前缀和，即为当前可能的最大子数组和max_sum=max(max_sum,prefix-min_prefix)# 更新历史最小前缀和，供下一个位置使用min_prefix=min(min_prefix,prefix)returnmax_sum

437. 路径总和 III (树上的前缀和)

题目描述：

给定一个二叉树的根节点root，和一个整数targetSum，求该二叉树里节点值之和等于targetSum的路径的数目。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

解题思路：

这道题是「560. 和为 K 的子数组」在树结构上的升级版。

解法为：前缀和 + DFS + 哈希表（回溯）。

1. 路径前缀和：在 DFS 遍历二叉树的过程中，维护从根节点到当前节点路径上的前缀和。
2. 目标查找：用哈希表记录该路径上各个前缀和出现的次数。若当前前缀和 - targetSum在哈希表中存在，则说明找到了一条或多条合法路径，累加数目。
3. 回溯清理（核心难点）：因为题目要求路径必须是向下的，所以左子树的路径不能跨越到右子树。当我们递归完某个节点准备向上返回（即退栈）时，必须将该节点贡献的前缀和从哈希表中减去，避免污染其他并列分支的计算。

核心代码：

importcollectionsfromtypingimportOptional# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclassSolution:defpathSum(self,root:Optional[TreeNode],targetSum:int)->int:# 处理空树边界ifnotroot:return0# 1. 初始化哈希表，记录从根到祖先节点的前缀和出现次数prefix_count=collections.defaultdict(int)prefix_count[0]=1# 默认前缀和为0出现1次# 2. 定义内部递归函数defdfs(node,curr_sum):ifnotnode:return0# 2.1 更新到达当前节点的前缀和curr_sum+=node.val# 2.2 查表：统计有多少个祖先节点的前缀和等于 curr_sum - targetSumvalid_paths=prefix_count[curr_sum-targetSum]# 2.3 将当前前缀和加入哈希表，供子节点查询prefix_count[curr_sum]+=1# 2.4 深入遍历左右子树，累加路径数valid_paths+=dfs(node.left,curr_sum)valid_paths+=dfs(node.right,curr_sum)# 2.5 回溯清理：该节点遍历完毕，将其前缀和记录撤销，不影响兄弟节点prefix_count[curr_sum]-=1returnvalid_pathsreturndfs(root,0)