前缀和算法


前缀和算法 是一种通过预处理数组,快速计算任意区间和的技巧。它能在 O(1) 时间复杂度内回答区间和的查询,适用于需要频繁计算子数组/子区间和的问题。以下是其核心应用场景、实现方法及经典例题:


一、适用场景

  1. 频繁查询区间和
    • 多次计算数组的某一子区间 [L, R] 的和。
  2. 统计满足条件的子数组数量
    • 例如“和为k的子数组数量”、“和为偶数的子数组数量”等。
  3. 处理环形数组或二维矩阵
    • 环形数组通过复制数组处理,二维矩阵扩展为二维前缀和。
  4. 结合哈希表优化查找
    • 寻找满足 preSum[j] - preSum[i] = target 的索引组合。

二、实现步骤

  1. 预处理前缀和数组
    • 定义 preSum[i] 表示数组前 i 项的和(索引通常从1开始)。
    • 递推公式:preSum[i] = preSum[i-1] + nums[i-1]
  2. 计算区间和
    • 区间 [L, R] 的和为 preSum[R+1] - preSum[L](左闭右闭区间)。
  3. 结合哈希表优化
    • 遍历时记录前缀和出现次数,快速统计满足条件的子数组。

三、经典例题与代码

1. 一维前缀和(区间和查询)
class PrefixSum:def __init__(self, nums):n = len(nums)self.preSum = [0] * (n + 1)for i in range(1, n+1):self.preSum[i] = self.preSum[i-1] + nums[i-1]def query(self, L, R):  # 闭区间 [L, R]return self.preSum[R+1] - self.preSum[L]# 示例
nums = [1, 2, 3, 4]
ps = PrefixSum(nums)
print(ps.query(1, 2))  # 输出 2+3=5
2. 统计和为k的子数组数量(哈希优化)
def subarraySum(nums, k):preSum = {0: 1}  # 初始前缀和为0出现1次current_sum = 0count = 0for num in nums:current_sum += num# 若 current_sum - target 存在,则存在子数组和为kcount += preSum.get(current_sum - k, 0)preSum[current_sum] = preSum.get(current_sum, 0) + 1return count# 示例
nums = [1, 1, 1]
print(subarraySum(nums, 2))  # 输出 2
3. 二维前缀和(矩阵区域和)
class MatrixPrefixSum:def __init__(self, matrix):m, n = len(matrix), len(matrix[0])self.preSum = [[0]*(n+1) for _ in range(m+1)]for i in range(1, m+1):for j in range(1, n+1):self.preSum[i][j] = matrix[i-1][j-1] + self.preSum[i-1][j] + self.preSum[i][j-1] - self.preSum[i-1][j-1]def query(self, x1, y1, x2, y2):  # 左上角(x1,y1),右下角(x2,y2)return self.preSum[x2+1][y2+1] - self.preSum[x1][y2+1] - self.preSum[x2+1][y1] + self.preSum[x1][y1]# 示例
matrix = [[1, 2, 3],[4, 5, 6],[7, 8, 9]
]
mps = MatrixPrefixSum(matrix)
print(mps.query(1, 1, 2, 2))  # 输出 5+6+8+9=28

四、常见问题与陷阱

  1. 索引偏移问题
    • 前缀和数组通常比原数组多一个元素,需注意索引转换(例如原数组的 nums[i] 对应 preSum[i+1])。
  2. 负数与哈希表结合
    • 当数组中存在负数时,前缀和可能重复,需用哈希表记录所有出现位置。
  3. 环形数组处理
    • 若数组是环形的(如 LeetCode 918),可将原数组复制一份拼接,转化为线性问题。

五、适用问题特征

  • 题目中出现 “子数组和”“连续区间和”“多次查询区间和” 等关键词。
  • 暴力解法时间复杂度为 O(n²),前缀和可优化至 O(n)O(1)

前缀和是解决子数组/子区间问题的利器,结合哈希表或二分查找可进一步扩展其应用场景。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/34531.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【JavaEE进阶】Spring事务

目录 🍃前言 🌴事务简介 🚩 什么是事务? 🚩为什么需要事务? 🚩事务的操作 🍀Spring 中事务的实现 🚩Spring 编程式事务 🚩Spring声明式事务Transactional 🚩T…

MySQL索引特性——会涉及索引的底层B+树

1 没有索引,可能会有什么问题 索引:提高数据库的性能,索引是物美价廉的东西了。不用加内存,不用改程序,不用调sql,只要执行正确的 create index ,查询速度就可能提高成百上千倍。但是天下没有免…

给单片机生成字库的方案

Python 这段代码用来将txt文件中储存的字符串转变成二进制的像素数据 from PIL import Image, ImageFont, ImageDraw import osdef find_microsoft_yahei():"""Windows系统定位微软雅黑字体"""font_paths ["C:/Windows/Fonts/msyh.ttc&q…

01Spring Security框架

Spring Security是什么? Spring Security是⼀个提供身份验证、授权和针对常见攻击的保护的框架。 Spring Security做什么? 作为开发⼈员,在⽇常开发过程中需要⽤到Spring Security的场景⾮常多。事实上,对Web应⽤程序⽽⾔&#xf…

「BWAPP靶场通关记录(1)」A1注入漏洞

BWAPP通关秘籍(1):A1 injection 1.HTML Injection - Reflected (GET)1.1Low1.2Medium1.3High 2.HTML Injection - Reflected (POST)2.1Low2.2Medium2.3High 3.HTML Injection - Reflected (URL)3.1Low3.2/3.3Medium/HIgh 4.HTML Injection - …

机器学习算法实战——敏感词检测(主页有源码)

✨个人主页欢迎您的访问 ✨期待您的三连 ✨ ✨个人主页欢迎您的访问 ✨期待您的三连 ✨ ✨个人主页欢迎您的访问 ✨期待您的三连✨ ​ ​​​ 1. 引言 随着互联网的快速发展,信息传播的速度和范围达到了前所未有的高度。然而,网络空间中也充斥着大量的…

Ollama+DeepSeek+NatCross内网穿透本地部署外网访问教程

目录 一、Ollama 简介 二、下载Ollama 三、下载并运行 DeepSeek 模型 四、运行 DeepSeek 模型 五、NatCross免费内网穿透 六、配置 ChatBox 连接 Ollama 七、外网使用ChatBox体验 一、Ollama 简介 Ollama 是一个开源的本地大模型部署工具,旨在让用户能够在个…

联想台式电脑启动项没有U盘

开机按F12,进入启动设备菜单,发现这里没有识别到插在主机的U盘? 解决方法 1、选上图的Enter Setup或者开机按F2,进入BIOS设置 选择Startup -> Primary Boot Sequence 2、选中“Excludeed from boot order”中U盘所在的一行 …

开源链动 2+1 模式 AI 智能名片 S2B2C 商城小程序助力社群发展中榜样影响力的提升

摘要:本文深入剖析了社群发展进程中榜样所承载的关键影响力,并对开源链动 21 模式 AI 智能名片 S2B2C 商城小程序在增强这一影响力方面所具备的潜力进行了全面探讨。通过对不同类型社群,如罗辑思维社群和 007 不出局社群中灵魂人物或意见领袖…

《交互式线性代数》

《交互式线性代数》 *Interactive Linear Algebra*由Dan Margalit和Joseph Rabinoff编写,是一本聚焦线性代数的教材。本书旨在教授线性代数的核心概念、方法及其应用,通过代数与几何相结合的方式,帮助读者深入理解线性代数的本质&#xff0c…

CSS -属性值的计算过程

目录 一、抛出两个问题1.如果我们学过优先级关系,那么请思考如下样式为何会生效2.如果我们学习过继承,那么可以知道color是可以被子元素继承使用的,那么请思考下述情景为何不生效 二、属性值计算过程1.确定声明值2.层叠冲突3.使用继承4.使用默…

生活中的可靠性小案例11:窗户把手断裂

窗户把手又断了,之前也断过一次,使用次数并没有特别多。上方的图是正常的把手状态,断的形状如下方图所示。 这种悬臂梁结构,没有一个良好的圆角过渡,导致应力集中。窗户的开关,对应的是把手的推拉&#xff…

怎么解决在Mac上每次打开文件夹都会弹出一个新窗口的问题

在Mac上每次打开文件夹都会弹出一个新窗口的问题,可以通过以下方法解决‌ ‌调整Finder设置‌: 打开Finder,点击“Finder”菜单,选择“偏好设置”。在偏好设置中,选择“通用”标签。取消勾选“在标签页中打开文件夹”或…

HOT100——栈篇Leetcode739. 每日温度

文章目录 题目:Leetcode160. 相交链表原题链接思路代码 题目:Leetcode160. 相交链表 给定一个整数数组 temperatures ,表示每天的温度,返回一个数组 answer ,其中 answer[i] 是指对于第 i 天,下一个更高温…

C++ 返回值优化(Return Value Optimization)

Intro 返回值优化(Return Value Optimization, RVO)是 C中的一种编译器优化技术, 它允许编译器在某些情况下省略临时对象的创建和复制/移动操作, 从而提高程序性能. RVO 主要应用于函数返回值的场景. 两种形式的 RVO 假定我们有这样一个类: class MyClass {std::string nam…

C++内存管理(复习)

1.动态申请多个某类型的空间并初始化 //动态申请10个int类型的空间并初始化为0到9int* p new int[10]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; delete[] p; //销毁 2.new/delete new:开空间构造函数 delete:析构函数释放空间 new和delete是用户进行动态内存申请和释放的操作符&#…

计算机视觉——深入理解卷积神经网络与使用卷积神经网络创建图像分类算法

引言 卷积神经网络(Convolutional Neural Networks,简称 CNNs)是一种深度学习架构,专门用于处理具有网格结构的数据,如图像、视频等。它们在计算机视觉领域取得了巨大成功,成为图像分类、目标检测、图像分…

Java数据结构第二十三期:Map与Set的高效应用之道(二)

专栏:Java数据结构秘籍 个人主页:手握风云 目录 一、哈希表 1.1. 概念 1.2. 冲突 1.3. 避免冲突 1.4. 解决冲突 1.5. 实现 二、OJ练习 2.1. 只出现一次的数字 2.2. 随机链表的复制 2.3. 宝石与石头 一、哈希表 1.1. 概念 顺序结构以及平衡树中…

OSPF | LSDB 链路状态数据库 / SPF 算法 / 实验

注:本文为 “OSPF | LSDB / SPF ” 相关文章合辑。 LSDB 和 SPF 算法 潇湘浪子的蹋马骨汤 发布 2019-02-15 23:58:46 1. 链路状态数据库 (LSDB) 链路状态协议除了执行洪泛扩散链路状态通告(LSA)以及发现邻居等任务外,其第三个任…

Android Framework 之了解系统启动流程二

Android Framework 源码阅读系列篇章有: 系统启动流程一之init进程和zygote进程启动分析系统启动流程二之SystemServer进程启动分析 1. SystemServer 进程启动分析 在 系统启动流程一之init进程和zygote进程启动分析 中分析 zygote 进程时,我们知道了…