前缀和(prefix sum)是算法题中比较实用嘚一种技巧当算法题的背景是整数型数组且出现 “子数组和” 或者 “连续的子数组” 既可以考虑使用前缀和来求解会得到不错的效果。
假设给定的数组A各个元素分别为:
那么我们可以得到一个前缀和数组B通过累加A[0:i-1]得到B[i]:
在实现上,可以直接在数组B的基础上累加即可不需偠遍历一遍A。
现在看一道简单的应用LeetCode 560. Subarray Sum Equals K。题目很简单找到连续子数组和为K的子数组个数。传统方法是两次循环时间复杂度O(
但是这里如果使用前缀和搭配HashMap可以实现O(n)的时间复杂度。