什么是前缀和

一种记录数组前n项和的数据结构

int n = nums.length;
//前缀和数组
int[] preSum =new int[n+1];
preSum[0]=0;
for(i=0;i<n;i++){
    preSum[i+1]=preSum[i]+nums[i];
}

那么利用前缀和可以解决一些子数组问题

例如求有多少子数组的和为k

很容易想到一个解法

int subarraySum(int[] nums,int k){
    int n = nums.length;
    int []sum=new int[n+1];
    sum[0]=0;
    for(int i=0; i < n; i++){
        sum[i+1]=sum[i]+num[i];
    }
    
    int ans;
    for(int i=1; i < n; i++){
        for(int j = 0; j < i; j++){
            if(sum[i]-sum[j] == k)
                ans++;
        }
    }
    return ans;
}
​

这个解法时间复杂度O(n^2) ，空间复杂度O(n)，并非最优解

我们可以进行一些优化

优化解法

对于前面的for

for(int i=1; i < n; i++)
        for(int j = 0; j < i; j++)
            if(sum[i]-sum[j] == k)
                ans++;

在枚举所有子数组，统计有多少 j 能使得 sum[i]-sum[j] 差为k

我们可以把if中的条件移项

if (sum[j] ==  sum[i] -k)
            ans++;

优化的思路是：直接记录下有几个sum[j]和sum[i]- k相等，直接更新结果，这样就避免了内层的for循环

我们可以用哈希表，记录前缀和的同时记录该前缀和出现的次数

int subarraySum(int[] nums, int k) {
    int n = nums.length;
    // map：前缀和 -> 该前缀和出现的次数
    HashMap<Integer, Integer> 
        preSum = new HashMap<>();
    // base case
    preSum.put(0, 1);
​
    int ans = 0, sum0_i = 0;
    for (int i = 0; i < n; i++) {
        sum0_i += nums[i];
        // 这是我们想找的前缀和 nums[0..j]
        int sum0_j = sum0_i - k;
        // 如果前面有这个前缀和，则直接更新答案
        if (preSum.containsKey(sum0_j))
            ans += preSum.get(sum0_j);
        // 把前缀和 nums[0..i] 加入并记录出现次数
        preSum.put(sum0_i, 
            preSum.getOrDefault(sum0_i, 0) + 1);
    }
    return ans;
}

比如说下面这个情况，需要前缀和 8 就能找到和为 k 的子数组了，之前的暴力解法需要遍历数组去数有几个 8，而优化解法借助哈希表可以直接得知有几个前缀和为 8。

这样，就把时间复杂度降到了 O(N)，是最优解法了。

三、总结

前缀和不难，却很有用，主要用于处理数组区间的问题。

比如说，让你统计班上同学考试成绩在不同分数段的百分比，也可以利用前缀和技巧：

int[] scores; // 存储着所有同学的分数
// 试卷满分 150 分
int[] count = new int[150 + 1]
// 记录每个分数有几个同学
for (int score : scores)
    count[score]++
// 构造前缀和
for (int i = 1; i < count.length; i++)
    count[i] = count[i] + count[i-1];

这样，给你任何一个分数段，你都能通过前缀和相减快速计算出这个分数段的人数，百分比也就很容易计算了。

但是，稍微复杂一些的算法问题，不止考察简单的前缀和技巧。比如本文探讨的这道题目，就需要借助前缀和的思路做进一步的优化，借助哈希表去除不必要的嵌套循环。可见对题目的理解和细节的分析能力对于算法的优化是至关重要的。

附上C代码

​
int subarraySum(int num[],int k){
    int n=sizeof(num)/sizeof(int);   
    int sum[9999]={0};
    sum[0]=0;
    for(int i=0; i < n; i++){
        sum[i+1] = sum[i]+ num[i];
    }//不写成函数时可以直接处理
     //num[i+1]+=num[i];
        
    int ans,k;
    scanf("%d",&k);
    for(int i=1; i < n; i++){
        for(int j = 0; j < i; j++){
            if(sum[i]-sum[j] == k)
                ans++;
        }
    }
    return ans;
}

#include<map>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
​
using namespace std;
​
int main(){
   //散列表
   unordered_map<int,int> preSum;
   preSum.insert(pair<int,int>(0,0));
   //前缀和初始化
   int num[9999]={0};
   int i=1,n,j;
   cin>>n;
   while (i<=n)
   {
      cin>>j;
      num[i]=j;
      num[i]+=num[i-1]; 
      preSum[num[i]]=0;
      i++;
   }
   int ans=0,k;
   scanf("%d",&k);
   int sumj;
   for(int q=0;q<i;q++){
         //要找的前缀和
         sumj=num[q]-k;
         //map里查找
         if(preSum.find(sumj)!=preSum.end()){
            //注：find返回一个指向sumj的迭代器
           ans+=preSum[sumj]; 
           
         }
         //加入当前
         preSum[num[q]]++;
​
   }
   printf("%d",ans);
   return 0;
}