本文简单描述一下前缀和算法
什么是前缀和
前缀和,顾明思议就是所有数组前缀的和,如果用数组pre表示,那么pre[i]就是nums[0]~nums[i]的和
前缀和应用
主要针对数组中连续子数组的和,就考虑前缀和
那么[j,i]之间的和就是pre[i] - pre[j-1]
对于求解连续子数组和为k的个数的问题, 以i结尾的和为k的连续子数组就是找到j使得pre[j-1] = pre[i] - k 也就是前缀和里面有多少个是pre[i] - k
如何快速的求解pre[j-1]呢?如果想实现O(1)的时间复杂度,就需要将pre的数据存储到map,map的key为pre[x],value为x即key为前缀和的值,value为出现该前缀和的数量。