【基础算法总结】前缀和二

news/2024/7/21 23:54:19/文章来源:https://blog.csdn.net/fight_p/article/details/139001776

前缀和二

  • 1.和为 K 的子数组
  • 2.和可被 K 整除的子数组
  • 3.连续数组
  • 4. 矩阵区域和

在这里插入图片描述

点赞👍👍收藏🌟🌟关注💖💖
你的支持是对我最大的鼓励,我们一起努力吧!😃😃

1.和为 K 的子数组

题目链接:560. 和为 K 的子数组

题目分析:

在这里插入图片描述
子数组是连续的!
在这里插入图片描述
算法原理:

解法一:暴力枚举

定位一个下标然后从前往后遍历,两层for循环把所有子数组都找出来,把和为k的数组个数统计一下。肯定能解决问题,但时间复杂度是O(N^2)。并且这道题要注意范围是从负数到整数,因此定位一个下标从前往后走,即使找到了也不能停下,还要继续往后面找。万一后面数是0呢,万一后面数加起来是0呢。所以每次都要找到结尾!

在这里插入图片描述
以前也做过找子数组和的问题,那个时候用的是滑动窗口,本质就是同向双指针,right不往回走,但是今天这道题就不行了,滑动窗口的使用:数组要具有单调性或者说数组内都是正整数(大于0)才能用!

这道题数组里面可能有0,可能有负数,现在left和right指向一个区间了,但是区间内部可能还有符合的,right必须要回去才行,因此 不能用滑动窗口优化。

在这里插入图片描述
解法二:前缀和

以i位置为结尾的所有子数组

我们暴力枚举是以某点为起点的子数组。这里我们以某点为结尾的子数组。
只看前面到这个点为结尾而不看从这个位置往后,也是可以把所有子数组都枚举出来的。那以某个点为结尾的子数组中找到和为K的子数组有多少个,然后把所有情况加起来。

在这里插入图片描述
我们把它抽象出来,先看以i为结尾的子数组,后面先不看

如果是直接从i往前找和等于K的就和暴力枚举没区别了,此时引入前缀和思想。当枚举到i位置时,我已经知道以i为结尾的前缀和,假设是 sum[i], 此时我们需要找一个区间和为K,那仅需找一个前缀和让它等于 sum[i]-K 不就可以了嘛 。

在这里插入图片描述

这样就转化为 在【0,n-1】区间内,有多少个前缀和等于 sum【i】- K
在这里插入图片描述

如果直接把前缀和数组搞出来然后找i位置之前有多少个前缀和等于sum[i]-k
,那还需要从前到i位置遍历,这样就比暴力枚举时间复杂度还高。没有必要。如果要快速查找一个东西可以使用哈希表。
在这里插入图片描述
因此解法二:前缀和+哈希表

细节问题:
1.前缀和加入哈希表的时机?

第一种就是把所有前缀和都算出来都加入到hash表在找,这种方式有问题,我要找i位置之前这样把i位置之后的和也加入到哈希表了,是有问题的。

在计算i位置之前,哈希表里面只保存 [0,i-1] 位置的前缀和,计算完i位置之和,才把i位置的前缀和加入哈希表。

2.不用真的创建一个前缀和数组,用一个变量 sum 来标记前一个位置的前缀和即可

3.如果到i位置整个前缀和等于K?
那是不是要去[0,-1] 去找0,但是没有这个区间,但是[0,i]等于k也是一种情况,因此hash表特殊处理 hash[0]=1

class Solution {
public:int subarraySum(vector<int>& nums, int k) {unordered_map<int,int> hash;//统计前缀和出现次数hash[0]=1;int sum=0,ret=0;for(auto& x:nums){sum+=x; //计算当前位置前缀和if(hash.count(sum-k)) ret+=hash[sum-k];//统计个数hash[sum]++;}return ret;}
};

2.和可被 K 整除的子数组

题目链接:974. 和可被 K 整除的子数组

题目描述:

在这里插入图片描述

这道题和上一道题没什么区别,一个让找和为k的子数组,一个让找能够被k整除的子数组。

算法原理:

解法一:暴力枚举
枚举出所有子数组,然后找到符合条件的子数组!

在说解法二之前有两个补充知识:

1.同余定理

在这里插入图片描述

2.C++,java 【负数 % 正数】的结果以及修正

在C++,java 中 负数 % 正数 = 负数 如果得到一个正数呢?
修正:(a%p+p)%p 负数->正数,正数即使多加了也会模掉结果不会变。

有了这两个就可以开始解法二了,这道题解法和前面一模一样

解法二:前缀和+哈希表

转化成以i结尾的子数组找子数组和能被k整除。
使用前缀和思想,得到以i为结尾的所有元素的和 sum[i] ,我们现在也知道i位置之前所有下标的前缀和,因此在i为结尾的子数组中找一个子数组和能被k整除,可以转换成 [0,i-1]找有多少个前缀和余数等于 (sum % k + k)% k (余数可能为负修正一下)

在这里插入图片描述
在使用哈希表 hash<int,int> 记录前缀和的余数 和 次数。
这里的细节问题和上面的一模一样。

class Solution {
public:int subarraysDivByK(vector<int>& nums, int k) {unordered_map<int,int> hash;hash[0%k]=1; //0%k这个数的余数int sum=0,ret=0;for(auto& x: nums){sum+=x;// 算出当前位置前缀和int mod=(sum%k+k)%k;//修正后的余数if(hash.count(mod)) ret+=hash[mod];//统计结果hash[mod]++;}return ret;}
};

3.连续数组

题目链接:525. 连续数组

题目描述:

在这里插入图片描述

题目很简单就是让找包含相同1和0个数的最大子数组的长度

算法原理:
这道题如果统计子数组中1和0个数,是很难的。对于这道题,我们可以使用 正难则反 ,正面解决麻烦转化一下在求解。
转化:
1.将所有的 0 修改成 -1
2.在数组中,找出最长的子数组,使子数组中所有元素的和为0
在这里插入图片描述

前面有道题是在数组种找和为k的子数组,这里解题思想是完全一样,转换成找和为0子数组。

解法:前缀和+哈希表

不过细节有些差别。

1.哈希表中存的是什么

这道题让找的是数组的长度。因此hash<int,int> 前面是前缀和,后面是下标

2.前缀和什么时候存入哈希表

在使用sum[i]之后,在丢入哈希表

3.如果有重复的 <sum,i> 怎么办
以i为结尾然后找的过程中出现以j为结尾的前缀和相等,但是因为我们要找到的是最长子数组长度,我们只保存前面的 <sum,j>

在这里插入图片描述

4.默认前缀和为0的情况,哈希表如何存

以i为结尾的子数组本身前缀和等于0,这时我们去的是【0,-1】区间找,以前存的是个数hash[0]=1默认有一个,今天这里是hash[0]=-1,存的是下标
在这里插入图片描述
5.长度如何计算

在这里插入图片描述

class Solution {
public:int findMaxLength(vector<int>& nums) {unordered_map<int,int> hash;hash[0]=-1; // 默认有一个前缀和为0的情况int sum=0,ret=0;for(int i=0;i<nums.size();++i){sum+=(nums[i]==0?-1:1);if(hash.count(sum)) ret=max(ret,i-hash[sum]);else hash[sum]=i;}return ret;}
};

4. 矩阵区域和

题目链接:1314. 矩阵区域和

题目分析:

在这里插入图片描述
这道题让返回一个数组,数组内每个下标的和是某一个区域的和。具体如下
通过两个例子,就可以理解上面的意思
在这里插入图片描述

可以看到求answer数组每个下标的值其实就是在求mat子矩阵的和!
关于子矩阵的和前面我们写过一道二维数组前缀和模板,可以用哪里的思想。

算法原理:

解法:前缀和

不要死记模板,自己分析。
如果要求子矩阵D的和,我们算出A+B+C+D的和,然后减去A+B的和,再减去A+C的和,但是多减了A的和,因此在加上一个A的和,最终就是区域D的和。但是前提是要知道A+B的和,A+C的和。

在这里插入图片描述

因此预先处理一个前缀和数组

在这里插入图片描述
预处理之后就该使用数组了
在这里插入图片描述
不用死记硬背我们自己也是可以推出来的,这里【x1,y1】,【x2,y2】我们要根基题意看是哪里。

在这里插入图片描述
但这里有些问题,上面的前缀和数组我们是从数组下标从【1,1】开始的。所以公式没有越界情况。但是这道题数组下标是从0开始的!

对于一维数组下标从0开始好解决,我们直接对第一个位置特殊处理一下。对于二维数组呢。如果把模板改成从0下标开始边界太难控制 ,因此我们多申请一行一列!让下标从1开始,那样上面的公式也不用大改了。
然后我们改一下下标标映射关系

在这里插入图片描述

class Solution {
public:vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {int m=mat.size(),n=mat[0].size();// 1.预处理前缀和数组vector<vector<int>> dp(m+1,vector<int>(n+1));for(int i=1;i<=m;++i)for(int j=1;j<=n;++j)dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+mat[i-1][j-1];// 2.使用vector<vector<int>> ret(m,vector<int>(n));for(int i=0;i<m;++i)for(int j=0;j<n;++j){int x1=max(0,i-k)+1,y1=max(0,j-k)+1;int x2=min(m-1,i+k)+1,y2=min(n-1,j+k)+1;ret[i][j]=dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1];}return  ret;}
};

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

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

相关文章

WPS PPT学习笔记 2 结构页的制作

制作PPT结构页 制作封面页、目录页、封底页。它们都属于结构页。而时间轴页&#xff0c;流程图页&#xff0c;框架图页这些属于内容页。 做一份PPT 讲一个故事 封面页 开头&#xff0c; 目录页 脉络&#xff0c; 各式内容页 详情&#xff0c; 封底页 结尾。 所有的结构页…

华为CE6851-48S6Q-HI升级设备版本及补丁

文章目录 升级前准备工作笔记本和交换机设备配置互联地址启用FTP设备访问FTP设备升级系统版本及补丁 升级前准备工作 使用MobaXterm远程工具连接设备&#xff0c;并作为FTP服务器准备升级所需的版本文件及补丁文件 笔记本和交换机设备配置互联地址 在交换机接口配置IP&#…

Ubuntu24.04安装tabby-terminal-1.0.207并处理依赖

1 下载 tabby-terminal-1.0.207 地址&#xff1a; https://github.com/Eugeny/tabby/releases 点击show all 36 assets 选择 tabby-1.0.207-linux-x64.deb 并下载。 2 依赖下载 gconf2_3.2.6-3ubuntu6_amd64.deb gconf2-common_3.2.6-3ubuntu6_all.deb gconf-service_3.2.6-…

fpga系列 HDL: 05 阻塞赋值(=)与非阻塞赋值(<=)

在Verilog硬件描述语言&#xff08;HDL&#xff09;中&#xff0c;信号的赋值方式主要分为两种&#xff1a;连续赋值和过程赋值。每种赋值方式有其独特的用途和语法&#xff0c;并适用于不同类型的电路描述。 1. 连续赋值&#xff08;Continuous Assignment,assign 和&#xf…

【Matlab函数分析】绘图函数:colormap查看并设置当前颜色图

&#x1f517; 运行环境&#xff1a;Matlab &#x1f6a9; 撰写作者&#xff1a;左手の明天 &#x1f947; 精选专栏&#xff1a;《python》 &#x1f525; 推荐专栏&#xff1a;《算法研究》 #### 防伪水印——左手の明天 #### &#x1f497; 大家好&#x1f917;&#x1f91…

云计算-基础云架构(Fundamental Cloud Architectures)

工作负载分配架构&#xff08;Workload Distribution Architecture&#xff09; 工作负载分配架构是一种基础架构&#xff0c;它在一组相同的IT资源之间分配负载。其结构如图7.1所示&#xff08;更好的图示在教材中&#xff09;。 图&#xff1a;工作负载分配架构 这个结构中的…

Elasticsearch之入门与安装

Elaticsearch&#xff0c;简称为es&#xff0c; es是一个开源的高扩展的分布式全文检索引擎&#xff0c;它可以近乎实时的存储、检索数据&#xff1b;本身扩展性很好&#xff0c;可以扩展到上百台服务器&#xff0c;处理PB级别的数据。es也使用Java开发并使用Lucene作为其核心来…

【源码】一站式Java云商城系统源码,无后门

一站式Java云商城系统源码&#xff0c;无后门&#xff0c;不是java源代码&#xff0c;是编译后的。 系统对接 手动发货 自动发货 兑 换 码 订单监控 商品监控 对象存储 邮箱提醒 加价模板 密价功能 三方支付 会员体系 财务明细 交易分析 售后服务 技术支持 服务器建议配置&a…

网易面试:手撕定时器

概述&#xff1a; 本文使用STL容器-set以及Linux提供的timerfd来实现定时器组件 所谓定时器就是管理大量定时任务&#xff0c;使其能按照超时时间有序地被执行 需求分析&#xff1a; 1.数据结构的选择&#xff1a;存储定时任务 2.驱动方式&#xff1a;如何选择一个任务并执…

微信小程序中van-tab的title(动态)根据文本内容,自适应宽度

小程序van-tab的title&#xff08;动态&#xff09;根据文本内容&#xff0c;自适应宽度 效果图代码主要调整点 效果图 代码 <van-tabs color"#00aaff" active"{{ active }}" bind:click"onTabChange"><van-tab title"7天内&quo…

mac版本Phpstudy本地环境安装Discuz教程【2024】

此方法适用于m1版本的mac版本Phpstudy本地环境安装Discuz&#xff0c;当然同样使用更高版本的mac端。网上各种安装教程参差不齐&#xff0c;根本解决不了小白的入门需求&#xff0c;以下是最新且直接明了的安装教程。 Phpstudy本地环境安装Discuz教程&#xff1a; 1、安装Phps…

Activiti7_使用

Activiti7_使用 一、Activiti7二、绘制工作流三、通过代码部署流程&#xff0c;再对流程进行实例化&#xff0c;完整运行一遍流程即可四、在springbooot中使用 一、Activiti7 为了实现后端的咨询流转功能&#xff0c;学习Activiti7&#xff0c;记录下使用的过程及遇到的问题 二…

小牛翻译:图片翻译API+语音翻译API调用,保姆级使用教程

一、小牛翻译接口简介 图片翻译API 支持格式&#xff1a;png、jpg、jpeg、bmp支持图片尺寸&#xff1a;128px*128px~2048px*2048px支持最大图片大小&#xff1a;10M支持的语种&#xff1a;中、英、日、韩、俄 语音翻译API 支持格式&#xff1a;MP3、WAV支持语音时长&#x…

根据经纬度点计算经纬度点之间的距离

根据经纬度点计算经纬度点之间的距离 根据两点经纬度坐标计算直线距离 根据经纬度点计算经纬度点之间的距离 根据经纬度计算两地之间的距离 根据两点经纬度坐标计算距离 其实看第一个就够了 根据 半正矢公式&#xff08;Haversine formula&#xff09;即可计算 本计算式选取地…

2024电激世界脉动-中国汽车品牌全球化制胜手册

来源&#xff1a;奥美Ogilvy&#xff1a; 近期历史回顾&#xff1a; 2024中国宏观经济专题报告-数据要素市场建设 2023-2024年度报告.pdf 2024制药与生化医疗技术产业链白皮书.pdf 从可再生能源到绿氢-中国投资助力埃及能源转型.pdf 2024有机旅行中国行业指引.pdf 2024中国技术…

【常用的队列总结】

文章目录 队列的介绍Queue队列的基本概念与操作队列的基本概念 常见的队列介绍非阻塞队列LinkedList:ArrayDeque:PriorityQueue: 阻塞队列ArrayBlockingQueueLinkedBlockingQueuePriorityBlockingQueue DelayQueueSynchronousQueue 队列的介绍 Queue队列的基本概念与操作 在 …

常见算法(1)

1.基本查找/顺序查找 核心&#xff1a;从0索引之后挨个查找 实现代码&#xff1a; public class test {public static void main(String [] arg) throws ParseException {int[] arr {121,85,46,15,55,77,63,49};int number55;System.out.println(bashi(arr,number));}publi…

多线程基本常识

多线程的状态 在Java中&#xff0c;一个线程的生命周期有以下几种状态&#xff1a; 新建&#xff08;New&#xff09;&#xff1a;当线程对象被创建时&#xff0c;线程处于新建状态。此时线程对象存在&#xff0c;但还没有调用start()方法启动线程。 运行&#xff08;Runnable…

ssm145基于java的电脑硬件库存管理系统+jsp

电脑硬件库存管理系统的设计与实现 摘 要 互联网发展至今&#xff0c;无论是其理论还是技术都已经成熟&#xff0c;而且它广泛参与在社会中的方方面面。它让信息都可以通过网络传播&#xff0c;搭配信息管理工具可以很好地为人们提供服务。针对电脑硬件库存信息管理混乱&…

SQL 语言:完整性约束

文章目录 概述主键 ( Primary Key ) 约束外键&#xff08;Foreign Key&#xff09;约束属性值上的约束全局约束总结 概述 数据库的完整性是指数据库正确性和相容性&#xff0c;是防止合法用户使用数据库时向数据库加入不符合语义的数据。保证数据库中数据是正确的&#xff0c;…