关于android:使用前缀和数组解决区间和查询问题

本文已收录到  GitHub · AndroidFamily，有 Android 进阶常识体系，欢送 Star。技术和职场问题，请关注公众号 [彭旭锐] 进 Android 面试交换群。

前言

大家好，我是小彭。

明天分享到一种十分乏味的数据结构 —— 前缀和数组。前缀和的思维自身很容易了解，同时也是了解更高难度的线段树、字典树等数据结构的根底。

那么，什么是前缀和，咱们能够应用前缀和解决什么问题呢？明天咱们就围绕这两个问题开展。

学习路线图：

1. 什么是前缀和

前缀和数组是一种用来高效地解决 “静态数据的频繁区间和查问” 问题的数据结构。

先举个例子，给定一个整数数组，要求输入数组在 $[i, j]$ 区间内元素的总和，这就是区间查问问题。这道题的暴力解法是很容易想到的，无非就是把 $[i, j]$ 区间中所有元素累计而已即可，工夫复杂度是 $O(n)$，空间复杂度是 $O(1)$。

单次查问的确曾经没有优化空间了，但如果进行频繁的区间和查问，很显著会有十分多反复的求和运算。例如，在查问 $[1, 5]$ 区间和 $[1, 10]$ 区间时，$[1, 5]$ 这个子区间就被反复计算了。那么，有可能借助 “空间换工夫”，在 $O(1)$ 工夫复杂度内计算 $[5000,1000000]$ 上的区间和吗？

这就须要应用前缀和 + 差分技巧：

• 预处理阶段： 开拓一个前缀和数组，记录每个地位到所有前驱节点的累加和 $preSum$，总共须要 O(n) 工夫；
• 查问阶段： 将区间左右端点的区间和相减，就能够在 $O(1)$ 工夫失去这个区间中所有元素的累加和，防止了每次查问都须要 for 循环遍历整个区间求和。例如，要求 $[i, j]$ 区间的和，就是间接用 $preSum[j + 1] - preSum[i]$ 取得。

前缀和示意图

2. 典型例题 · 区间和检索

了解以上概念后，就曾经具备解决区间和问题的基本知识了。咱们来看一道 LeetCode 上的前缀和典型例题：LeetCode 303. 区域和检索 - 数组不可变

LeetCode 例题

题解

class NumArray(nums: IntArray) {    // 前缀和数组    // 数组长度加一后不必思考数组越界，代码更简洁    private val preSum = IntArray(nums.size + 1) { 0 }    init {        for (index in nums.indices) {            preSum[index + 1] = preSum[index] + nums[index]        }    }    fun sumRange(i: Int, j: Int): Int {        return preSum[j + 1] - preSum[i]    }}

代码很简略，其中前缀和数组 preSum 的长度要额定加 1 是为了简化数组越界判断。咱们来剖析它的复杂度：

• 工夫复杂度： 构建前缀和数组的工夫复杂度是 $O(n)$，查问的工夫复杂度是 $O(m)$，$n$ 是数据量，$m$ 是区间和查问的次数；
• 空间复杂度： $O(n)$，应用了 长度为 $n+ 1$ 的前缀和数组。

另外，前缀和还实用于二维区间和检索，思路都是相似的，你能够试试看： LeetCode · 304. 二维区域和检索 - 矩阵不可变

3. 典型例题 · 前缀和 + 哈希表

持续看另一道前缀和与哈希表联合的例题：LeetCode 560. 和为 K 的子数组

LeetCode 例题

这道题就是在考前缀和思维，咱们能够轻松地写出第一种解法：

题解

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    }}

在这个题解中，咱们枚举每个子数组，应用「前缀和 + 差分」技巧计算区间和为 K 的个数，咱们来剖析下它的复杂度：

• 工夫复杂度： 一共存在 $n^2$ 个子数组，单次子数组的区间查问是 $O(1)$，所以整体的工夫复杂度是 $O(n^2)$；
• 空间复杂度： $O(n)$。

工夫复杂度有方法优化吗？咱们发现，题目要求的是数组个数，而不关怀具体的数组，所以咱们不用枚举全副子数组（一共有 $n^2$ 个子数组）， 咱们只须要在计算出以后地位的前缀和之后，察看之前的地位中是否存在前缀和正好等于 $preSum[j] - K$ 的地位，有的话，就阐明它们之间的区间和就是 $K$。 把满足条件的个数累加起来，就是最终后果。

前缀和示意图

紧接着另一个问题是：怎么疾速找到前缀和等于 $preSum[j] - K$ 的地位？聪慧的你肯定晓得了—— 哈希表。 咱们能够保护一个哈希表，记录前缀和呈现的地位，就能够用 O(1) 找到它。 因为前缀和有可能会反复呈现，而且咱们只关怀次数不关怀地位，所以映射关系应该为 <前缀和 - 呈现次数>。

题解

class Solution {    fun subarraySum(nums: IntArray, k: Int): Int {        var preSum = 0        var result = 0        // 保护哈希表<前缀和，呈现次数>        val map = HashMap<Int, Int>()        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)$。

4. 典型例题 · 前缀和 + 枯燥队列

持续看一道前缀和与枯燥队列联合的例题，你能够先做一下第 53 题：

• LeetCode 53. 最大子数组和
• LeetCode 918. 环形子数组的最大和

LeetCode 例题

在第 53 题中，咱们只须要保护一个以后察看到的最小前缀和变量，将其与以后的前缀和做差值，就能够失去以以后节点为右端点的最大的区间和。这一题就是考前缀和思维，绝对简略。

第 53 题题解

class Solution {    fun maxSubArray(nums: IntArray): Int {        // 前缀和 + 枯燥：保护最小的前缀和        var minPreSum = 0        var result = Integer.MIN_VALUE        var preSum = 0        for (element in nums) {            preSum += element            result = Math.max(result, preSum - minPreSum)            minPreSum = Math.min(minPreSum, preSum)        }        return result    }}

在第 918 题中，数组变为环形数组，环形数组的问题个别都会用 2 倍的 “假数据长度” 做模仿，求前缀和数组这一步大同小异。

关键在于： “子数组最多只能蕴含固定缓冲区 num 中的每个元素一次”，这象征随着察看的区间右节点逐步向右挪动，所容许的左区间会限度在一个滑动窗口范畴内，以防止元素反复呈现。因而，一个变量不再可能满足题目需要。

示意图

所以咱们的问题就是要求这个 “滑动窗口中的最小前缀和”。Wait a minute! 滑动窗口的最小值？这不就是 应用枯燥队列解决 “滑动窗口最大值” 问题 这篇文章讲的内容吗，秒懂，枯燥队列安顿一下。

第 918 题题解

class Solution {    fun maxSubarraySumCircular(nums: IntArray): Int {        val preSum = IntArray(nums.size * 2 + 1).apply {            for (index in 0 until nums.size * 2) {                this[index + 1] = this[index] + nums[index % nums.size]            }        }        // 枯燥队列（从队头到队尾递增）        val queue = LinkedList<Int>()        var result = Integer.MIN_VALUE        for (index in 1 until preSum.size) {            // if：移除队头超出滑动窗口范畴的元素            // 前缀和窗口 k 为 length + 1，比原数组上的逻辑窗口大 1 位，因为区间的差值要找前一个节点的前缀和            if (!queue.isEmpty() && queue.peekFirst() < index - nums.size /* index - k + 1 */) {                queue.pollFirst()            }            // 从队头取指标元素            result = Math.max(result, preSum[index] - (preSum[queue.peekFirst() ?: 0]))            // while：队尾元素大于以后元素，阐明队尾元素不再可能是最小值，后续不再思考它            while (!queue.isEmpty() && preSum[queue.peekLast()] >= preSum[index]) {                // 摈弃队尾元素                queue.pollLast()            }            queue.offerLast(index)        }        return result    }}

咱们来剖析它的工夫复杂度：

• 工夫复杂度： 构建前缀和数组 $O(n)$，前缀和数组中每个元素在枯燥队列中入队和出队 $1$ 次，因而整体工夫复杂度是 $O(n)$;
• 空间复杂度： 构建前缀和数组 $O(n)$，最坏状况下（递加序列）所有元素都被增加到枯燥队列中，因而整体空间复杂度是 $O(n)$。

提醒： 这道题还有应用 Kadane 算法 的 $O(1)$ 空间复杂度解法。

5. 总结

到这里，前缀和的内容就讲完了。文章结尾也提到了， 前缀和数组是一种高效地解决静态数据的频繁区间和查问问题的数据结构，只须要结构一次前缀和数组，就能应用 O(1) 工夫实现查问操作。

那么，在动态数据的场景中（即动静减少或删除元素），应用前缀和数组进行区间和查问是否还放弃高效呢？如果不够高效，有其余的数据结构能够解决吗？你能够思考以下 2 道题：

• LeetCode · 307. 区域和检索 - 数组可批改
• LeetCode · 308. 二维区域和检索 - 矩阵不可变

更多同类型题目：

参考资料

• LeetCode 专题 · 前缀和 —— LeetCode 出品
• LeetCode 题解 · 560. 和为 K 的子数组 —— liweiwei1419 著
• 小而美的算法技巧：前缀和数组 —— labuladong 著
• 小而美的算法技巧：差分数组 —— labuladong 著