【Deprecated】算法 100000 个数的求和只

发表于

提示：这篇文章是 21 年写的，今年对此进行重写并增加了更多新思考：使用前缀和数组解决”区间和查询”问题

⭐️ 本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 和 [BaguTree Pro] 知识星球提问。

前言

  • 前缀和是一种非常适合处理 区间查询 问题的算法技巧，理解前缀和的思想对后续学习 线段树、字典树 很有帮助；
  • 在这篇文章里，我将梳理前缀和的基本知识 & 常考题型。如果能帮上忙，请务必点赞加关注，这真的对我非常重要。

目录

  1. 前缀和 + 差分

首先，我们使用一道典型例题来引入前缀和的概念。

303. 区域和检索 - 数组不可变 【题解】

给定一个整数数组 nums，求出数组从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点。

这道题的暴力解法是很容易想到的，区间[i,j][i, j][i,j]的和无非就是累加区间元素即可，时间复杂度是O(n)O(n)O(n)，空间复杂度是O(1)O(1)O(1)。但如果多次检索区间[i,j][i, j][i,j]的和，暴力解法就显得不优雅了，因为暴力解法中存在 很多重复求和运算。举个例子，暴力解法计算区间[1,5][1, 5][1,5]和区间[1,10][1, 10][1,10]，区间[1,5][1, 5][1,5]的元素就重复执行了求和运算。

那么，有没有办法优化区间和的时间复杂度呢？在 O(1)O(1)O(1) 时间复杂度内计算[5000,1000000][5000,1000000][5000,1000000]的区间和，有可能吗？方法总是有的，无非是利用空间换取时间，这就需要使用「前缀和 + 差分」技巧了。

前缀和的基本套路是开辟一个前缀和数组，存储「元素所有前驱节点的和」，例如：

1
2
3
4
5
scss复制代码val sum = IntArray(nums.size + 1) { 0 }

for (index in nums.indices) {
    sum[index + 1] = sum[index] + nums[index]
}

利用前缀和数组，可以很快计算出区间 [i, j] 的和：nums[i,j]=preSum[j+1]−preSum[i]nums[i, j] = preSum[j + 1] - preSum[i]nums[i,j]=preSum[j+1]−preSum[i]

参考代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
kotlin复制代码class NumArray(nums: IntArray) {
    private val sum = IntArray(nums.size + 1) { 0 }

    init {
        for (index in nums.indices) {
            sum[index + 1] = sum[index] + nums[index]
        }
    }

    fun sumRange(i: Int, j: Int): Int {
        return sum[j + 1] - sum[i] // 注意加一
    }
}

提示： 前缀和数组长度不一定要比原数组长度大 1，加 1 的目的是为了在后面做差分的时候代码会比较简洁。

另外，前缀和还适用于二维区间和检索，思路都是类似的，你可以试试看：

304. 二维区域和检索 - 矩阵不可变 【题解】
  1. 前缀和 + 哈希表优化

这一节我们来讨论前缀和结合哈希表的优化技巧，这种技巧一般是适用在一些 只关心次数，不关心具体的解 的场景。利用哈希表 O(1)O(1)O(1) 时间复杂度查询的特性，可以进一步优化时间复杂度。

同样地，我们使用一道典型例题来展开讨论：

560. 和为K的子数组 【题解】

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

示例 1 :

输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。

题目的要求是计算和为 k 的子数组个数，掌握了使用前缀和计算区间和后，我们可以轻松地写出一种解法：在这里我们枚举每个子数组，使用「前缀和 + 差分」技巧计算区间和为 kkk 的个数：

参考代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
kotlin复制代码class Solution {
    fun subarraySum(nums: IntArray, k: Int): Int {
        1、预处理：构造前缀和数组
        var preSum = IntArray(nums.size + 1) { 0 }
        for (index in nums.indices) {
            preSum[index + 1] = preSum[index] + nums[index]
        }

        2、枚举所有子数组，使用「前缀和 + 差分」技巧计算区间和
        var result = 0
        for (i in nums.indices) {
            for (j in i until nums.size) {
                val sum_i_j = preSum[j + 1] - preSum[i]
                if (k == sum_i_j) {
                    result++
                }
            }
        }
        return result
    }
}

整个算法的时间复杂度是O(n2)O(n^2)O(n2)，空间复杂度是O(n)O(n)O(n)，这是最优算法了吗？因为题目要求的是数组个数，而不关心具体的数组，所以我们大可不必枚举全部子数组（一共有n2n^2n2个子数组），我们只需要在计算出当前位置的前缀和之后，观察之前位置符合条件的前缀和个数即可。

具体来说，对于当前位置已经计算出前缀和 preSum[j]preSum[j]preSum[j]，我们只需要寻找在[0,j−1][0, j -1][0,j−1]区间内，前缀和为preSum[j]−kpreSum[j] - kpreSum[j]−k 的个数。

紧接着的问题是：怎么快速查找前缀和为preSum[j]−kpreSum[j] - kpreSum[j]−k 的个数呢？聪明的你一定知道是哈希表了，我们需要维护一个哈希表：Key 为前缀和，Value 为前缀和出现次数。

参考代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
kotlin复制代码class Solution {
    fun subarraySum(nums: IntArray, k: Int): Int {
        var preSum = 0
        var result = 0

        维护一个哈希表：Key 为前缀和，Value 为前缀和出现次数
        val map = HashMap<Int, Int>()
        在索引 0 之前，存在一个前缀和为 0 的空数组
        map[0] = 1

        for (index in nums.indices) {
            preSum += nums[index]

            查询前缀和为 preSum - k 的个数
            val offset = preSum - k
            if (map.contains(offset)) {
                result += map[offset]!!
            }

            map[preSum] = map.getOrDefault(preSum, 0) + 1
        }

        return result
    }
}

如此，整个算法的时间复杂度降低为O(n)O(n)O(n)，空间复杂度保持为O(n)O(n)O(n)。

  1. 举一反三
525. 连续数组 【题解】
1004. 最大连续1的个数 III
1248. 统计「优美子数组」
974. 和可被 K 整除的子数组
352. 和等于 K 的最长子数组长度
1314. 矩阵区域和
  1. 总结
  • 前缀和技巧适用于区间查询等问题，当问题中提到 “连续子数组” 时，可以考虑使用「前缀和 + 差分」技巧；
  • 在只关心次数，不关心具体的解的场景，可以使用前缀和 + 哈希表进一步优化时间复杂度；
  • 前面提到的问题都属于静态数据场景，也就是前缀和只需要计算一次即可。如果数据是动态的呢，还可以使用前缀和吗？你可以思考下这两道题。
307. 区域和检索 - 数组可修改
308. 二维区域和检索 - 矩阵不可变

参考资料

创作不易，你的「三连」是丑丑最大的动力，我们下次见！

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%