当前位置: 首页 > news >正文

LeetCode-刷题记录-前缀和合集(本篇blog会持续更新哦~)

一、前缀和(Prefix Sum)算法概述

前缀和算法通过预先计算数组的累加和,可以在常数时间内回答多个区间和相关的查询问题,是解决子数组和问题中的重要工具。

在这里插入图片描述

它的基本思想是通过预先计算和存储数组的前缀和,可以在 O(1) 的时间复杂度内计算任意子数组的和。

在这里插入图片描述

  1. 定义
    • 对于数组 nums,其前缀和 prefix[i] 定义为从数组起始位置到第 i 个元素的累加和。

在这里插入图片描述

  • 具体公式:prefix[i] = nums[0] + nums[1] + ... + nums[i]
  1. 计算方法
    • 首先,创建一个额外的数组或哈希表,用来存储每个位置的前缀和。
    • 通过一次遍历数组,依次计算并填充这个数组或哈希表。

在这里插入图片描述

  1. 应用
    • 快速计算子数组和:通过前缀和,可以快速计算任意子数组的和。例如,子数组 nums[l...r] 的和可以通过 prefix[r] - prefix[l-1] 来计算,其中 lr 分别是子数组的左右边界。

在这里插入图片描述

  • 解决相关问题:例如,最大子数组和、和为特定值的子数组个数等问题,都可以通过前缀和算法高效解决。

在这里插入图片描述


二、前缀和习题合集

1. LeetCode 930 和相同的二元子数组

在这里插入图片描述

  • 思路:

假设原数组的前缀和数组为 sum,且子数组 (i,j] 的区间和为 goal,那么 sum[j]−sum[i]=goal。因此我们可以枚举 j ,每次查询满足该等式的 i 的数量。

用哈希表记录每一种前缀和出现的次数,假设我们当前枚举到元素 nums[j],我们只需要查询哈希表中元素 sum[j]−goal 的数量即可,这些元素的数量即对应了以当前 j 值为右边界的满足条件的子数组的数量。

  • pre[j] - pre[i]= goal —> pre[i] = pre[j] - goal

  • 如果存在前缀和为 pre[j] - goal(也就是pre[i])

  • 说明从某个位置 j 到当前位置 i 的子数组和为 goal

最后这些元素的总数量即为所有和为 goal 的子数组数量。

  • 代码:

class Solution {public int numSubarraysWithSum(int[] nums, int goal) {int n = nums.length; // 数组的长度Map<Integer,Integer> map = new HashMap<>(); // 使用哈希表来记录前缀和的出现次数int pre_J = 0; // 初始前缀和为0int ans = 0; // 计数器,用来记录符合条件的子数组个数for (int i = 0; i < n; i++) {map.put(preJ, map.getOrDefault(pre_J, 0) + 1); // 更新前缀和为 preJ 的出现次数pre_J += nums[i]; // 计算当前位置的前缀和//pre[j] - pre[i]= goal //pre[i] = pre[j] - goal// 计算满足条件的子数组个数// 如果存在前缀和为 pre[j] - goal(也就是pre[i])//说明从某个位置 j 到当前位置 i 的子数组和为 goalans += map.getOrDefault(pre_J - goal, 0);}return ans; // 返回符合条件的子数组个数}
}

2. LeetCode 560 和为K的子数组

在这里插入图片描述

  • 这里咋一看好像是可以用滑动窗口哈 ,但是发现数据里有负数。因为nums[i]可以小于0,也就是说右指针j向后移1位不能保证区间会增大,左指针i向后移1位也不能保证区间和会减小。

  • 思路 : 同上一题类似

前缀和 + 哈希

class Solution {public static int subarraySum(int[] nums, int k) {int n = nums.length; // 获取数组长度Map<Integer,Integer> map = new HashMap<>(); // 创建哈希表,用于存储前缀和及其出现次数int sum = 0; // 初始化前缀和为0int ans = 0; // 初始化结果为0map.put(sum,1); // 将初始的前缀和0放入哈希表,并设其出现次数为1// 遍历数组for(int num : nums){sum += num; // 计算当前位置的前缀和// 如果哈希表中存在前缀和为sum-k的项,则说明存在和为k的子数组 sum - (sum-k) = kif(map.containsKey(sum - k)){ans += map.get(sum - k); // 更新结果,累加前缀和为sum-k的子数组数量}map.put(sum, map.getOrDefault(sum, 0) + 1); // 更新哈希表,将当前前缀和放入,并更新出现次数}return ans; // 返回结果}
}
  • 初始时,将前缀和为 0 放入哈希表 map 中,表示在初始状态下存在一个前缀和为 0 的情况,出现次数为 1。

  • 如果 map 中存在 sum - k,则说明从之前的某个位置到当前位置的子数组的和为 k。这是因为 sum - (sum - k) = k

  • 如果存在这样的前缀和,则将该前缀和的出现次数累加到 ans 中。


3. LeetCode 523 连续的子数组和

在这里插入图片描述

在这里插入图片描述

  • 这里要用到数学知识——同余定理

在这里插入图片描述

  1. 前缀和的定义:preSum[i] 表示 nums 数组从 0 到 i 的元素之和。

    • 如果存在一个子数组 nums[j..i] (j < i),其和是 k 的倍数,则 preSum[i] - preSum[j-1] 必须是 k 的倍数。
  2. 利用余数的性质(同余定理)

    • 如果 preSum[i]preSum[j-1]k 取余得到相同的结果,即 (preSum[i] - preSum[j-1]) % k == 0,则存在这样的子数组。
    • a%k = b%k ,则 (a-b)%k =0 满足条件

在这里插入图片描述

  1. 使用哈希表记录余数: 使用哈希表来记录每个余数第一次出现的位置。

class Solution {public boolean checkSubarraySum(int[] nums, int k) {int n = nums.length;int[] pre = new int[n + 1];for (int i = 1; i <= n; i++) {pre[i] = pre[i - 1] + nums[i - 1]; // 计算前缀和}Set<Integer> set = new HashSet<>();for (int i = 2; i <= n; i++) {set.add(pre[i - 2] % k); // 将前缀和前两项的同余结果加入集合if (set.contains(pre[i] % k)) return true; // 如果当前前缀和对k取模的结果在集合中已经存在,说明找到了符合条件的子数组}return false; // 如果遍历完没有找到符合条件的子数组,返回false}
}

4. LeetCode 724 寻找数组的中心下标

在这里插入图片描述

  • 前缀和思想

法一:

class Solution {public static int pivotIndex(int[] nums) {int n = nums.length;int[] sumLeft = new int[n]; // 用于存储每个索引位置左侧元素之和int[] sumRight = new int[n]; // 用于存储每个索引位置右侧元素之和sumLeft[0] = 0; // 初始化左侧和数组的第一个元素为0(因为第一个元素左侧没有元素)sumRight[n - 1] = 0; // 初始化右侧和数组的最后一个元素为0(因为最后一个元素右侧没有元素)int sum1 = 0; // 用于计算累积的左侧和int sum2 = 0; // 用于计算累积的右侧和// 计算每个索引位置左侧的累积和for (int i = 0; i < n; i++) {sum1 += nums[i];sumLeft[i] = sum1;}// 计算每个索引位置右侧的累积和for (int i = n - 1; i >= 0; i--) {sum2 += nums[i];sumRight[i] = sum2;}// 遍历数组,找到第一个满足左侧和等于右侧和的索引位置for (int i = 0; i < n; i++) {if (sumLeft[i] == sumRight[i]) {return i;}}// 如果没有找到满足条件的索引,返回-1return -1;}
}

法二:

class Solution {public static int pivotIndex(int[] nums) {int totalSum = 0; // 计算整个数组的和for (int num : nums) {totalSum += num;}int leftSum = 0; // 左侧和的初始值为0for (int i = 0; i < nums.length; i++) {int rightSum = totalSum - leftSum - nums[i]; // 右侧和等于总和减去左侧和和当前数字if (leftSum == rightSum) {return i; // 如果左右两侧和相等,则返回当前索引作为轴心索引}leftSum += nums[i]; // 更新左侧和,将当前数字累加到左侧和中}return -1; // 如果遍历完整个数组都没有找到轴心索引,则返回-1表示不存在}
}

5. LeetCode 238 除自身以外数组的乘积

在这里插入图片描述

  • 思路 :前缀积 + 后缀积 (左右乘积列表)

我们不必将所有数字的乘积除以给定索引处的数字得到相应的答案,而是利用索引左侧所有数字的乘积和右侧所有数字的乘积(即前缀与后缀)相乘得到答案。

注意这里有一个细节就是要除了自己,所以在累乘的时候,要在当前位置保存 左侧 或者 右侧 (不包含自己)。

前积乘后积,先存后乘避开自己

class Solution {public int[] productExceptSelf(int[] nums) {int n= nums.length;// L 和 R 分别表示左右两侧的乘积列表int[] L = new int[n];int[] R = new int[n];int[] answer = new int[n];// L[i] 为索引 i 左侧所有元素的乘积// 对于索引为 '0' 的元素,因为左侧没有元素,所以 L[0] = 1L[0] = 1;for (int i = 1; i < n; i++) {L[i] = nums[i - 1] * L[i - 1];}// R[i] 为索引 i 右侧所有元素的乘积// 对于索引为 'n-1' 的元素,因为右侧没有元素,所以 R[length-1] = 1R[n- 1] = 1;for (int i = n- 2; i >= 0; i--) {R[i] = nums[i + 1] * R[i + 1];}// 对于索引 i,除 nums[i] 之外其余各元素的乘积就是左侧所有元素的乘积乘以右侧所有元素的乘积for (int i = 0; i < n; i++) {answer[i] = L[i] * R[i];}return answer;}
}

class Solution {public int[] productExceptSelf(int[] nums) {int length = nums.length;int[] answer = new int[length];// answer[i] 表示索引 i 左侧所有元素的乘积// 因为索引为 '0' 的元素左侧没有元素, 所以 answer[0] = 1answer[0] = 1;for (int i = 1; i < length; i++) {answer[i] = nums[i - 1] * answer[i - 1];}// R 为右侧所有元素的乘积// 刚开始右边没有元素,所以 R = 1int R = 1;for (int i = length - 1; i >= 0; i--) {// 对于索引 i,左边的乘积为 answer[i],右边的乘积为 Ranswer[i] = answer[i] * R;// R 需要包含右边所有的乘积,所以计算下一个结果时需要将当前值乘到 R 上R *= nums[i];}return answer;}
}

更新于:

在这里插入图片描述

本篇blog会持续更新哦~

相关文章:

LeetCode-刷题记录-前缀和合集(本篇blog会持续更新哦~)

一、前缀和&#xff08;Prefix Sum&#xff09;算法概述 前缀和算法通过预先计算数组的累加和&#xff0c;可以在常数时间内回答多个区间和相关的查询问题&#xff0c;是解决子数组和问题中的重要工具。 它的基本思想是通过预先计算和存储数组的前缀和&#xff0c;可以在 O(1)…...

【中项第三版】系统集成项目管理工程师 | 第 4 章 信息系统架构③ | 4.6

前言 第4章对应的内容选择题和案例分析都会进行考查&#xff0c;这一章节属于技术相关的内容&#xff0c;学习要以教材为准。本章分值预计在4-5分。 目录 4.6 网络架构 4.6.1 基本原则 4.6.2 局域网架构 4.6.3 广域网架构 4.6.4 移动通信网架构 4.6.5 软件定义网络 4.6…...

知识图谱入门笔记

自学参考&#xff1a; 视频&#xff1a;斯坦福CS520 | 知识图谱 最全知识图谱综述 详解知识图谱的构建全流程 知识图谱构建&#xff08;概念&#xff0c;工具&#xff0c;实例调研&#xff09; 一、基本概念 知识图谱&#xff08;Knowledge graph&#xff09;&#xff1a;由结…...

常见的气体流量计有哪些?

1.气体涡轮流量计 适用场合&#xff1a;流量变化小&#xff0c;脉动流频率小&#xff0c;中低压洁净天然气优点 1.精度高&#xff0c;重复性好 2.测量范围广&#xff0c;压损小&#xff0c;安装维修方便 3.具有较高的抗电磁干扰和抗震动能力缺点&#xff1a;分辨率低&#xff…...

AI推介-大语言模型LLMs论文速览(arXiv方向):2024.07.01-2024.07.05

文章目录&#xff5e; 1.LLM Internal States Reveal Hallucination Risk Faced With a Query2.Fine-Tuning with Divergent Chains of Thought Boosts Reasoning Through Self-Correction in Language Models3.Investigating Decoder-only Large Language Models for Speech-t…...

Android IP地址、子网掩码、默认网关、首选DNS服务器、备用DNS服务器校验

Android IP地址、子网掩码、默认网关、首选DNS服务器、备用DNS服务器校验 public String isIP(String ip) {String regex = "(25[0-5]|2[0-4]\\d|1\\d{2}|[1-9]?\\d)(\\.(25[0-5]|2[0-4]\\d|1\\d{2}|[1-9]?\\d)){3}";Pattern p = Pattern.compile(regex)...

铁威马NAS教程丨为什么修复文件系统、为卷扩容、增加及删除 SSD 缓存等操作失败?

适用机型&#xff1a; 所有 TNAS 型号 适用版本&#xff1a; 所有 TOS 版本 问题现象&#xff1a; 在尝试修复文件系统、为卷扩容、增加或删除 SSD 缓存时(TOS 5)&#xff0c;可能因卷被其他进程占用而操作失败。 解决方法&#xff1a; 为了成功执行上述操作&#xff0c;您…...

【深度学习】第3章——回归模型与求解分析

一、回归分析 1.定义 分析自变量与因变量之间定量的因果关系&#xff0c;根据已有的数据拟合出变量之间的关系。 2.回归和分类的区别和联系 3.线性模型 4.非线性模型 5.线性回归※ 面对回归问题&#xff0c;通常分三步解决 第一步&#xff1a;选定使用的model&#xff0c;…...

Maven的基本使用

引入依赖 1.引入Maven仓库存在的依赖&#xff0c;直接引入&#xff0c;刷新Maven <dependency><groupId>org.springframework</groupId><artifactId>spring-webmvc</artifactId><version>5.2.12.RELEASE</version> </dependency…...

【笔记】finalshell中使用nano编辑器GNU

ctrl O 保存 enter 确定 ctrl X 退出 nano编辑 能不用就不用吧 因为我真用不习惯 nano编辑的文件也可以用vim编辑的...

markdown文件转pdf

步骤&#xff1a;md转html转pdf pom引入 <!--markdown 转pdf--><dependency><groupId>com.vladsch.flexmark</groupId><artifactId>flexmark-all</artifactId><version>0.64.8</version></dependency><dependency&g…...

课设:二手车交易管理系统(Java+MySQL)

简易数据库课程设计~分享 技术栈 本项目使用以下技术栈构建&#xff1a; Java: 作为主要编程语言&#xff0c;负责业务逻辑的实现。MySQL: 用于数据存储&#xff0c;管理用户、车辆和订单信息。JDBC: 用于Java与MySQL数据库之间的连接和操作。Swing GUI: 提供用户图形界面&am…...

vue3实现无缝滚动 列表滚动 vue3-seamlessscroll

vue3框架内使用无缝滚动&#xff0c;使用一个插件比较合适&#xff08;gitee地址&#xff09;&#xff1a; vue3-seamless-scroll: Vue3.0 无缝滚动组件 具体更多配置请看&#xff1a; 组件配置 | vue3-scroll-seamless 1. 安装&#xff1a; npm install vue3-seamless-sc…...

Python酷库之旅-第三方库Pandas(012)

目录 一、用法精讲 28、pandas.HDFStore.keys函数 28-1、语法 28-2、参数 28-3、功能 28-4、返回值 28-5、说明 28-6、用法 28-6-1、数据准备 28-6-2、代码示例 28-6-3、结果输出 29、pandas.HDFStore.groups函数 29-1、语法 29-2、参数 29-3、功能 29-4、返回…...

SpringCloud集成nacos之jasypt配置中心的密码加密的自动解密

目录 1.引入相关的依赖 2.nacos的yaml的相关配置&#xff0c;配置密码和相关算法 3.配置数据源连接 3.1 数据库连接配置 4.连接数据库配置类详解&#xff08;DataSourceConfig&#xff09;。 5.完整的配置类代码如下 1.引入相关的依赖 <dependency><groupId>…...

Python 中将字典内容保存到 Excel 文件使用详解

概要 在数据处理和分析的过程中,经常需要将字典等数据结构保存到Excel文件中,以便于数据的存储、共享和进一步分析。Python提供了丰富的库来实现这一功能,其中最常用的是pandas和openpyxl。本文将详细介绍如何使用这些库将字典内容保存到Excel文件中,并包含具体的示例代码…...

libaom 编码器 aomenc 使用文档介绍

使用方法&#xff1a;./aomenc <选项> -o 目标文件名 源文件名 使用 --help 查看完整的选项列表。 选项&#xff1a; --help 显示使用选项并退出-c <参数>, --cfg<参数> 使用配置文件-D, --debug 调试模式&#xff08;使输出确定性&#xff09;-o <参数&g…...

速盾:cdn 缓存图片

现如今&#xff0c;互联网已经成为我们日常生活中不可或缺的一部分。在我们使用互联网时&#xff0c;经常会遇到图片加载缓慢、文章打开慢等问题。为了解决这些问题&#xff0c;CDN&#xff08;内容分发网络&#xff09;应运而生。CDN 是一种通过将数据缓存在世界各地的服务器上…...

移动应用开发课设——原神小助手文档(2)

2023年末&#xff0c;做的移动应用开发课设&#xff0c;分还算高&#xff0c;项目地址&#xff1a;有帮助的话&#xff0c;点个赞和星呗~ GitHub - blhqwjs/-GenShin_imp: 2023年移动应用开发课设 本文按照毕业论文要求来写&#xff0c;希望对大家有所帮助。 接上文&#xff1a…...

智能聊天机器人:使用PyTorch构建多轮对话系统

使用PyTorch构建多轮对话系统的示例代码。这个示例项目包括一个简单的Seq2Seq模型用于对话生成&#xff0c;并使用GRU作为RNN的变体。以下是代码的主要部分&#xff0c;包括数据预处理、模型定义和训练循环。 数据预处理 首先&#xff0c;准备数据并进行预处理。这部分代码假…...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

《Playwright:微软的自动化测试工具详解》

Playwright 简介:声明内容来自网络&#xff0c;将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具&#xff0c;支持 Chrome、Firefox、Safari 等主流浏览器&#xff0c;提供多语言 API&#xff08;Python、JavaScript、Java、.NET&#xff09;。它的特点包括&a…...

五年级数学知识边界总结思考-下册

目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解&#xff1a;由来、作用与意义**一、知识点核心内容****二、知识点的由来&#xff1a;从生活实践到数学抽象****三、知识的作用&#xff1a;解决实际问题的工具****四、学习的意义&#xff1a;培养核心素养…...

数据库分批入库

今天在工作中&#xff0c;遇到一个问题&#xff0c;就是分批查询的时候&#xff0c;由于批次过大导致出现了一些问题&#xff0c;一下是问题描述和解决方案&#xff1a; 示例&#xff1a; // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...

mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包

文章目录 现象&#xff1a;mysql已经安装&#xff0c;但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时&#xff0c;可能是因为以下几个原因&#xff1a;1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文全面剖析RNN核心原理&#xff0c;深入讲解梯度消失/爆炸问题&#xff0c;并通过LSTM/GRU结构实现解决方案&#xff0c;提供时间序列预测和文本生成…...

2025季度云服务器排行榜

在全球云服务器市场&#xff0c;各厂商的排名和地位并非一成不变&#xff0c;而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势&#xff0c;对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析&#xff1a; 一、全球“三巨头”…...

智能AI电话机器人系统的识别能力现状与发展水平

一、引言 随着人工智能技术的飞速发展&#xff0c;AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术&#xff0c;在客户服务、营销推广、信息查询等领域发挥着越来越重要…...