标签搜索

目 录CONTENT

文章目录

前缀和技巧.md

小小城
2021-08-22 / 0 评论 / 0 点赞 / 5 阅读 / 2,647 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

前缀和技巧

先看一道题
在这里插入图片描述

一道简单却十分巧妙的算法问题:算出一共有几个和为 k 的子数组。

那我把所有子数组都穷举出来,算它们的和,看看谁的和等于 k 不就行了。关键是,如何快速得到某个子数组的和呢,比如说给你一个数组 nums,让你实现一个接口 sum(i, j),这个接口要返回 nums[i..j] 的和,而且会被多次调用,你怎么实现这个接口呢?

因为接口要被多次调用,显然不能每次都去遍历 nums[i..j],有没有一种快速的方法在 $O(1)$ 时间内算出 nums[i..j] 呢?这就需要前缀和技巧了。

一、什么是前缀和

前缀和的思路是这样的,对于一个给定的数组 nums,我们 ==额外开辟一个前缀和数组进行预处理==

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

在这里插入图片描述

这个前缀和数组 preSum 的含义也很好理解,preSum[i] 就是 nums[0..i-1] 的和。那么如果我们想求 nums[i..j] 的和,只需要一步操作 preSum[j+1]-preSum[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] + nums[i];

    int ans = 0;
    // 穷举所有子数组
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < i; j++)
            // sum of nums[j..i-1]
            if (sum[i] - sum[j] == k)
                ans++;

    return ans;
}

这个解法的时间复杂度 $O(N^2)$ 空间复杂度 $O(N)$,并不是最优的解法。

二、优化解法

优化这段代码:

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

第二层 for 循环在干嘛呢?翻译一下就是,在计算,有几个 j 能够使得 sum[i] 和 sum[j] 的差为 k。毎找到一个这样的 j,就把结果加一

我们可以把 if 语句里的条件判断移项,这样写:

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

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

我们先来分析一下, 如果区间[left, right]中数字之和等于k, 那么是不是会有sum(right) - sum(left) == k,这样就变成了sum(right) - k == sum(left)

我们用一个字典当做累积和, 对于nums = [1,1,-2,2,4,-2,2], k=2来说,累积和[1,2,0,2,6,4,6],这里我们用字典dict记录一下每个累积和出现的次数,考虑到了累积和刚好等于k的情况,将dict初始化为{0:1}

下面我们来遍历一下nums,看看具体情况:

SUM = 0,SUM - k = -2 没有出现在dict中,  count = 0,  dict = {0:1}(base case)
SUM = 1, SUM - k = -1 没有出现在dict中, count = 0,  dict = {0:1, 1:1}
SUM = 2, SUM - k = 0  出现在了dict中,   count = 1,  dict = {0:1,1:1,2:1}
SUM = 0, SUM - k = -2 没有出现在dict中, count = 1,  dict = {0:2,1:1,2:1}
SUM = 2, SUM - k = 0  出现在了dict中,   count = 3,   dict = {0:2,1:1,2:2}
SUM = 6, SUM - k = 4  没有出现在dict中, count = 3,   dict = {0:2,1:1,2:2,6:1}
SUM = 4, SUM - k = 2  出现在了dict中,   count = 5,   dict = {0:2,1:1,2:2,6:1,4:1}
SUM = 6, SUM - k = 4  出现在了dict中,   count = 6,   dict = {0:2,1:1,2:2,6:2,4:1}

所以count最后为6!!

其实分析下来,我们发现dict的作用就是记录sum(left)出现的次数这种方法只要遍历一遍数组就行!!

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

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];

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

0

评论区