前缀和
今天来聊一道简单却十分巧妙的算法问题:算出一共有几个和为 k 的子数组。
那我把所有子数组都穷举出来,算它们的和,看看谁的和等于 k 不就行了。
关键是,如何快速得到某个子数组的和呢,比如说给你一个数组 nums
,让你实现一个接口 sum(i, j)
,这个接口要返回 nums[i..j]
的和,而且会被多次调用,你怎么实现这个接口呢?
因为接口要被多次调用,显然不能每次都去遍历 nums[i..j]
,有没有一种快速的方法在 O(1) 时间内算出 nums[i..j]
呢?这就需要前缀和技巧了。