刷题面经神器Kotlin版前缀和速通

前缀和是什么？——附 Kotlin 实现示例

什么是前缀和？一份新手友好指南

如果你正在学习算法，或者准备刷题面试，大概率已经听说过前缀和这个概念。它是一种简单却非常强大的技巧，能高效解决数组求和、区间查询这类的各种问题。

本文我们就来拆解：前缀和到底是什么，它为什么好用，以及如何用代码实现它。

🔍 前缀和的定义

前缀和（也叫累积和）是一个新数组，其中每一个位置存储了原数组从开头到该索引的所有元素的总和。

对于原数组 arr，索引 i 位置的前缀和，就是原数组从索引 0 到 i 所有元素的加和，公式可以表示为：

prefix[i] = arr[0] + arr[1] +...+ arr[i]

举个例子

假设我们有这么一个数组：

arr = [3, 2, 5, 1, 7]

计算得到的前缀和数组就是：

prefix = [3, 5, 10, 11, 18]

计算过程一步一步看就是：

prefix[0] = 3
prefix[1] = 3 + 2 = 5
prefix[2] = 5 + 5 = 10
prefix[3] = 10 + 1 = 11
prefix[4] = 11 + 7 = 18

前缀和有什么用？

前缀和最大的优势在于：只需要一次预处理，之后就可以在常数时间 O(1) 内算出任意子数组的和。

不用前缀和是什么情况？

如果你要求索引 i 到 j 之间的元素和，你需要循环遍历这个区间里的每一个元素，最坏情况下时间复杂度是 O(n)。如果要多次查询不同区间，耗时会指数级上涨。

用了前缀和是什么情况？

有了前缀和数组，索引 i 到 j 的区间和就可以直接用这个公式算出：

sum(i, j) = prefix[j] - prefix[i -1]

如果 i == 0，那直接就是 sum(0, j) = prefix[j] 就行。

这个优化直接把每次查询的时间复杂度从 O(n) 降到了 O(1)！

🧠 Kotlin 实现前缀和（附示例）

下面是用 Kotlin 构建前缀和数组的代码，其实这就是力扣第 303 题「区域和检索 – 数组不可变」的标准答案：

classNumArray(  
    val nums: IntArray  
) {  
      
    private val prefixSum = IntArray(nums.size +1)  
  
    init {  
        // 一次遍历完成预处理，时间复杂度 O(N)
        var sum=0for (i in nums.indices) {  
            sum+= nums[i]  
            prefixSum[i +1] =sum  
        }  
    }  
  
    // 利用前缀和，每次查询都是 O(1) 时间复杂度
    fun sumRange(left: Int, right: Int): Int {  
        return prefixSum[right +1] - prefixSum[left]  
    }  
}

注：上面代码给前缀和数组多开了一个长度，prefixSum[0] 存0，简化了边界条件的判断，写起来更简洁不容易出错

🔄 前缀和的常见变种

二维前缀和：用于解决矩阵相关的区域求和问题
二进制前缀和：用于处理二进制/布尔数组类题目
前缀异或：解决基于异或运算的子数组查询问题

🧪 可以用前缀和解决的经典题目

区域和查询
和为 K 的子数组
区间和的个数
寻找数组的中心下标
数组的平衡索引

📝 总结

前缀和是算法解题中非常基础的工具。不管你是处理简单的区间和查询，还是给复杂算法做优化，前缀和都能让你的代码更高效、更优雅。

下次当你遇到需要重复计算区间和的问题时，不妨先问问自己：这里能不能用前缀和优化？十有八九，答案都是可以的！

原文链接：https://medium.com/@natig.haciyef/what-is-prefix-sum-in-kotlin-with-example-a9f332ba8796