前缀和技巧

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

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

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

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

    前缀和技巧 - 图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];
    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++;
    16.     return ans;
    17. }

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

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

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

    1.     ans++;

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

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

    这样，就把时间复杂度降到了 $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++)

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

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

    希望本文对你有帮助。

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

    labuladong

    上一篇：烧饼排序

    目录