前缀和技巧

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

前缀和技巧 - 图1

那我把所有子数组都穷举出来,算它们的和,看看谁的和等于 k 不就行了。

关键是,如何快速得到某个子数组的和呢,比如说给你一个数组 nums,让你实现一个接口 sum(i, j),这个接口要返回 nums[i..j] 的和,而且会被多次调用,你怎么实现这个接口呢?

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

一、什么是前缀和

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

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

前缀和技巧 - 图2

这个前缀和数组 preSum 的含义也很好理解,preSum[i] 就是 nums[0..i-1] 的和。那么如果我们想求 nums[i..j] 的和,只需要一步操作 preSum[j+1]-preSum[i] 即可,而不需要重新去遍历数组了。

回到这个子数组问题,我们想求有多少个子数组的和为 k,借助前缀和技巧很容易写出一个解法:

  1. int subarraySum(int[] nums, int k) {
  2. int n = nums.length;
  3. // 构造前缀和
  4. int[] sum = new int[n + 1];
  5. sum[0] = 0;
  6. for (int i = 0; i < n; i++)
  7. sum[i + 1] = sum[i] + nums[i];
  8. int ans = 0;
  9. // 穷举所有子数组
  10. for (int i = 1; i <= n; i++)
  11. for (int j = 0; j < i; j++)
  12. // sum of nums[j..i-1]
  13. if (sum[i] - sum[j] == k)
  14. ans++;
  15. return ans;
  16. }

这个解法的时间复杂度 $O(N^2)$ 空间复杂度 $O(N)$,并不是最优的解法。不过通过这个解法理解了前缀和数组的工作原理之后,可以使用一些巧妙的办法把时间复杂度进一步降低。

二、优化解法

前面的解法有嵌套的 for 循环:

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

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

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

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

优化的思路是:我直接记录下有几个 sum[j]sum[i] - k 相等,直接更新结果,就避免了内层的 for 循环。我们可以用哈希表,在记录前缀和的同时记录该前缀和出现的次数。

  1. int subarraySum(int[] nums, int k) {
  2. int n = nums.length;
  3. // map:前缀和 -> 该前缀和出现的次数
  4. HashMap<Integer, Integer>
  5. preSum = new HashMap<>();
  6. // base case
  7. preSum.put(0, 1);
  8. int ans = 0, sum0_i = 0;
  9. for (int i = 0; i < n; i++) {
  10. sum0_i += nums[i];
  11. // 这是我们想找的前缀和 nums[0..j]
  12. int sum0_j = sum0_i - k;
  13. // 如果前面有这个前缀和,则直接更新答案
  14. if (preSum.containsKey(sum0_j))
  15. ans += preSum.get(sum0_j);
  16. // 把前缀和 nums[0..i] 加入并记录出现次数
  17. preSum.put(sum0_i,
  18. preSum.getOrDefault(sum0_i, 0) + 1);
  19. }
  20. return ans;
  21. }

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

前缀和技巧 - 图3

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

三、总结

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

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

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

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

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

希望本文对你有帮助。

坚持原创高质量文章,致力于把算法问题讲清楚,欢迎关注我的公众号 labuladong 获取最新文章:

labuladong

上一篇:烧饼排序

下一篇:字符串乘法

目录