一种记录数组前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;
}
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;
}