esc to dismiss

前缀和

前缀和一般跟哈希表结合优化使用,否则前缀和跟暴力的枚举差别不大。

详细介绍参见 560. 和为K的子数组 的结题思路。

前缀和即对数列计算从开头到当前元素的累加值,由于可复用前序序列的前缀和,即第 i 个元素的前缀和 pre[i] = pre[i-1] + num[i]

而使用哈希表主要是为了保存统计前缀和(或一些变通:如前缀和求余等)出现次数(或下标等)。

x