IT技术博客大学习 共学习 共进步
首页 / 算法

算法模式：前缀和

"地瓜哥"博客网 2026-06-03 09:03:23 累计浏览 3 次
本机暂存
标签 前缀和 差分数组 数组 算法模式

在上一篇文章 算法模式：差分数组，本篇文章，继续介绍数组相关的算法模式：前缀和。

前缀和

前缀和可以简单理解为「数列的前 n 项的和」。具体过程如图所示：

前缀和
图 1. 前缀和

这是一种重要的预处理方式，也就是需要额外的空间并且提前计算好这些值。如果使用得当，能大大降低查询的时间复杂度。

LeetCode 303. 区域和检索 - 数组不可变

LeetCode - 303. 区域和检索 - 数组不可变

给定一个整数数组 nums，处理以下类型的多个查询:

  1. 计算索引 left 和 right （包含 left 和 right）之间的 nums 元素的 和 ，其中 left <= right

实现 NumArray 类：

  • NumArray(int[] nums) 使用数组 nums 初始化对象

  • int sumRange(int left, int right) 返回数组 nums 中索引 left 和 right 之间的元素的 总和，包含 left 和 right 两点（也就是 nums[left] + nums[left + 1] + …​ + nums[right] )

建议继续学习

  1. 为什么数组标号是从0开始的？ （累计阅读 6,241）
  2. php 返回目录下的所有文件名/文件夹类 （累计阅读 4,382）
  3. Java程序员们最常犯的3个集合错误 （累计阅读 4,101）
  4. “C++的数组不支持多态”？ （累计阅读 3,723）
  5. 关于Cannot use a scalar value as an array的解决办法 （累计阅读 3,501）
  6. javascript运算/转换技巧 （累计阅读 3,460）
  7. php中数组与字符串 （累计阅读 3,380）
  8. c、cpp中使用匿名结构体、类定义数组 （累计阅读 2,921）
  9. 深入理解PHP之数组(遍历顺序) （累计阅读 2,861）
  10. php数组的字符型索引是否应该遵循变量命名规则？ （累计阅读 2,760）