1. 前缀和算法核心思想解析前缀和Prefix Sum是算法竞赛和面试刷题中极为重要的预处理技术。我第一次系统学习这个概念是在准备北美大厂面试时当时被一道看似简单的数组求和问题卡了整整两小时直到发现前缀和这个解题神器。简单来说前缀和就是把原始数组进行预处理生成一个新数组其中每个元素存储原数组从起始位置到当前位置的累加和。比如对于数组 [1, 2, 3, 4]其前缀和数组就是 [1, 3, 6, 10]。这个看似简单的转换却能让许多复杂问题的求解时间复杂度从O(n²)骤降到O(n)。关键理解前缀和的本质是用空间换时间通过O(n)的预处理时间将后续的区间求和操作优化为O(1)的常数时间查询。2. 前缀和的经典应用场景2.1 区间求和问题这是前缀和最直接的应用场景。假设需要频繁查询数组某个区间的和比如计算arr[i...j]的和。传统做法是每次遍历区间计算时间复杂度O(n)。而使用前缀和后def range_sum(pre_sum, i, j): return pre_sum[j] - (pre_sum[i-1] if i 0 else 0)这个操作的时间复杂度是O(1)对于需要上万次查询的场景性能提升极其显著。2.2 二维矩阵区域求和前缀和可以扩展到二维情况。假设有个m×n的矩阵我们预处理一个前缀和矩阵prefix其中prefix[i][j]表示从(0,0)到(i,j)矩形区域内所有元素的和。这样计算任意子矩阵的和只需要def area_sum(prefix, x1, y1, x2, y2): return prefix[x2][y2] - (prefix[x1-1][y2] if x10 else 0) - (prefix[x2][y1-1] if y10 else 0) (prefix[x1-1][y1-1] if x10 and y10 else 0)2.3 滑动窗口优化很多滑动窗口问题可以通过前缀和哈希表的方式优化。比如LeetCode 560题和为K的子数组暴力解法是O(n²)而使用前缀和哈希可以优化到O(n)。3. 前缀和的实现细节与变种3.1 基础实现模板def build_prefix(arr): prefix [0] * len(arr) prefix[0] arr[0] for i in range(1, len(arr)): prefix[i] prefix[i-1] arr[i] return prefix3.2 环形数组处理对于环形数组常用的技巧是复制数组使其长度翻倍。比如原始数组是[1,2,3]处理为[1,2,3,1,2,3]然后正常计算前缀和。3.3 差分数组这是前缀和的逆操作常用于区间更新问题。差分数组diff[i] arr[i] - arr[i-1]对差分数组求前缀和就能还原原始数组。4. LeetCode典型题目解析4.1 简单题303. 区域和检索 - 数组不可变这是最基础的前缀和应用直接套用模板即可。关键点在于处理i0时的边界条件。4.2 中等题560. 和为K的子数组这道题的优化解法需要结合哈希表def subarraySum(nums, k): from collections import defaultdict prefix_sum defaultdict(int) prefix_sum[0] 1 current_sum 0 count 0 for num in nums: current_sum num count prefix_sum.get(current_sum - k, 0) prefix_sum[current_sum] 1 return count4.3 难题1074. 元素和为目标值的子矩阵数量这道题需要二维前缀和哈希表的组合技巧。先计算每行的前缀和再枚举所有可能的列组合。5. 前缀和问题解题框架识别问题类型当题目涉及连续子数组、区间和、频繁查询等关键词时考虑前缀和构建前缀数组根据问题维度选择一维或二维前缀和设计查询方式确定如何利用前缀数组快速得到答案处理边界条件特别注意i0或j0的情况优化空间复杂度有时可以不用存储整个前缀数组只需维护当前前缀和6. 常见错误与调试技巧索引越界前缀和数组通常比原数组长1第一个元素为0容易混淆初始化错误忘记初始化prefix[0] 0或prefix[0][0] 0整数溢出当元素值很大时前缀和可能超出整数范围哈希表遗漏在类似560题的问题中忘记初始化hashmap[0]1调试时可以打印出构建的前缀数组验证正确性对小规模测试用例手动计算验证特别注意循环的起始和终止条件7. 前缀和的扩展应用7.1 树上前缀和在树结构中前缀和可以用于快速计算路径和。通过DFS遍历记录从根节点到当前节点的路径和。7.2 带权前缀和当元素有不同权重时可以构建加权前缀和。比如计算区间平均值时可以同时维护元素和与个数两个前缀数组。7.3 多维前缀和三维甚至更高维的前缀和在图像处理、科学计算中有广泛应用。构建时需要多层循环嵌套。在实际刷题过程中我发现很多难题的解法都是前缀和与其他技巧如双指针、哈希表、二分查找的组合。掌握前缀和的本质后可以灵活应用到各种变种问题中。 
长河君 · 2026/11/3 12:27:30 · 阅读 1.2k 前缀和算法：原理、应用与LeetCode实战
1. 前缀和算法核心思想解析前缀和Prefix Sum是算法竞赛和面试刷题中极为重要的预处理技术。我第一次系统学习这个概念是在准备北美大厂面试时当时被一道看似简单的数组求和问题卡了整整两小时直到发现前缀和这个解题神器。简单来说前缀和就是把原始数组进行预处理生成一个新数组其中每个元素存储原数组从起始位置到当前位置的累加和。比如对于数组 [1, 2, 3, 4]其前缀和数组就是 [1, 3, 6, 10]。这个看似简单的转换却能让许多复杂问题的求解时间复杂度从O(n²)骤降到O(n)。关键理解前缀和的本质是用空间换时间通过O(n)的预处理时间将后续的区间求和操作优化为O(1)的常数时间查询。2. 前缀和的经典应用场景2.1 区间求和问题这是前缀和最直接的应用场景。假设需要频繁查询数组某个区间的和比如计算arr[i...j]的和。传统做法是每次遍历区间计算时间复杂度O(n)。而使用前缀和后def range_sum(pre_sum, i, j): return pre_sum[j] - (pre_sum[i-1] if i 0 else 0)这个操作的时间复杂度是O(1)对于需要上万次查询的场景性能提升极其显著。2.2 二维矩阵区域求和前缀和可以扩展到二维情况。假设有个m×n的矩阵我们预处理一个前缀和矩阵prefix其中prefix[i][j]表示从(0,0)到(i,j)矩形区域内所有元素的和。这样计算任意子矩阵的和只需要def area_sum(prefix, x1, y1, x2, y2): return prefix[x2][y2] - (prefix[x1-1][y2] if x10 else 0) - (prefix[x2][y1-1] if y10 else 0) (prefix[x1-1][y1-1] if x10 and y10 else 0)2.3 滑动窗口优化很多滑动窗口问题可以通过前缀和哈希表的方式优化。比如LeetCode 560题和为K的子数组暴力解法是O(n²)而使用前缀和哈希可以优化到O(n)。3. 前缀和的实现细节与变种3.1 基础实现模板def build_prefix(arr): prefix [0] * len(arr) prefix[0] arr[0] for i in range(1, len(arr)): prefix[i] prefix[i-1] arr[i] return prefix3.2 环形数组处理对于环形数组常用的技巧是复制数组使其长度翻倍。比如原始数组是[1,2,3]处理为[1,2,3,1,2,3]然后正常计算前缀和。3.3 差分数组这是前缀和的逆操作常用于区间更新问题。差分数组diff[i] arr[i] - arr[i-1]对差分数组求前缀和就能还原原始数组。4. LeetCode典型题目解析4.1 简单题303. 区域和检索 - 数组不可变这是最基础的前缀和应用直接套用模板即可。关键点在于处理i0时的边界条件。4.2 中等题560. 和为K的子数组这道题的优化解法需要结合哈希表def subarraySum(nums, k): from collections import defaultdict prefix_sum defaultdict(int) prefix_sum[0] 1 current_sum 0 count 0 for num in nums: current_sum num count prefix_sum.get(current_sum - k, 0) prefix_sum[current_sum] 1 return count4.3 难题1074. 元素和为目标值的子矩阵数量这道题需要二维前缀和哈希表的组合技巧。先计算每行的前缀和再枚举所有可能的列组合。5. 前缀和问题解题框架识别问题类型当题目涉及连续子数组、区间和、频繁查询等关键词时考虑前缀和构建前缀数组根据问题维度选择一维或二维前缀和设计查询方式确定如何利用前缀数组快速得到答案处理边界条件特别注意i0或j0的情况优化空间复杂度有时可以不用存储整个前缀数组只需维护当前前缀和6. 常见错误与调试技巧索引越界前缀和数组通常比原数组长1第一个元素为0容易混淆初始化错误忘记初始化prefix[0] 0或prefix[0][0] 0整数溢出当元素值很大时前缀和可能超出整数范围哈希表遗漏在类似560题的问题中忘记初始化hashmap[0]1调试时可以打印出构建的前缀数组验证正确性对小规模测试用例手动计算验证特别注意循环的起始和终止条件7. 前缀和的扩展应用7.1 树上前缀和在树结构中前缀和可以用于快速计算路径和。通过DFS遍历记录从根节点到当前节点的路径和。7.2 带权前缀和当元素有不同权重时可以构建加权前缀和。比如计算区间平均值时可以同时维护元素和与个数两个前缀数组。7.3 多维前缀和三维甚至更高维的前缀和在图像处理、科学计算中有广泛应用。构建时需要多层循环嵌套。在实际刷题过程中我发现很多难题的解法都是前缀和与其他技巧如双指针、哈希表、二分查找的组合。掌握前缀和的本质后可以灵活应用到各种变种问题中。