首页 > 其他分享 >前缀和的一些笔记

前缀和的一些笔记

时间:2024-04-28 18:01:23浏览次数:29  
标签:最早 前缀 位置 笔记 累加 哈希 一些 出现

左神课程笔记,前缀和笔记,(前缀和也是想双指针一样管理两个指针之间的区间的)

前缀和(前i个数的和)

个人理解,把前缀和当成两个指针,维护一个区间,例如 i - 1 到 i 这两个双指针之间管理的线段上放着一个a[i-1],感觉差分也能这样理解,a[i - 1 ] - a[i] 之间放着一个差分值

下标i结尾的往左边的 = aim的最长前缀和,思考转换以及思考前缀和性质-->转换为从0开始到右边的最早的前缀和 = sum - aim的位置,只关心最早的,这样才能转换成i结尾往左最大前缀和长度

 

查出前缀和最早的出现的位置,就能知道往左衍生多少就能凑出这个前缀和了

最早的表是什么,就是哈希表

用哈希表记录前缀和最早的位置,map提前放一条记录

 

哈希表记录最早出现的位置(哈希表有没有出现过,没有出现过就是最早位置,出现过了就不管了,永远记录最早的位置,只关心i结尾往左最长,查表就能搞定)

0前缀和一定要放-1位置,前0个数值已经确定了,0前缀和最早出现在哪里,没有就错过答案

 

0累加和没有数的时候就出现过了,加了记录就不会出现错误

-1位置最早凑出0,-1位置下面一个就是我的答案(0-0),map放一条记录

 

前缀和为0最早出现在-1位置,sum =5,aim=5,5-5最早出现在哪里,出现-1,所以0到当前结尾位置就是我的最大长度

 

利用哈希表管理最早出现的位置,每个位置以i为结尾的最长下标

往左逆向为从0开始往右最早的前缀和,前缀和以及最早出现的位置

累加和为给定值的子数组数量,哈希表的应用很关键

某一个累加和最早出现的次数,某一个累加和出现了几次

 

0-i累加和一千,想看整体的累加和,转换,用哈希表的思想,因为我们不要求具体的值

算整体累加和,i结尾子数组累加和100,也就是900这个前缀和出现了几次

累加和以及出现次数(0前缀和没数字时候已经有一次了

前缀和-目标之前出现过几次(0位置多少个,1位置多少个,2..所有位置一共多少个

总体的累加次数,哈希表记录数据的思想,但是我还是不理解,以i结尾,我之前出现过的前缀和为多少个,注意是以i为结尾,所以就遍历i on(两数之和问题,a+b = c转换成a-c = b(遍历a,用哈希表记录值,查看b有没有出现过,如果出现过就加上对应的次数,a随着遍历会改变,b也会改变,只看哈希表有没有出现过(遇到两数之和类似的问题,就用哈希表,这样把两个指针优化到一个指针,只用关心当前出现的值在哈希表中有没有出现过即可,然后把当前出现的值加入哈希表表示出现次数

标签:最早,前缀,位置,笔记,累加,哈希,一些,出现
From: https://www.cnblogs.com/zhoncai45/p/18164238

相关文章

  • c#学习笔记
    程序程序集是代码进行编译是的一个逻辑单元,把相关的代码和类型进行组合,然后生成PE文件。程序集只是逻辑上的划分 【公共语言运行库CLR】加载器管理应用程序域,这种管理包括将每个程序集加载到相应的应用程序域以及控制每个程序集中类型层次结构的内存布局 一个程序运行......
  • 《期货-市场技术分析》读书笔记
    第二本技术分析书籍,《期货-市场分析技术》:书中的很多内容,如趋势、趋势线、阻力、支撑等,也象《日本蜡烛图》一样,没有逻辑推理过程,没有数据验证。但是我认可其确实有一定的心理暗示作用。因为我在听很多技术分析大V的视频时,他们中的大部分人,确实也都是这么分析的。如果大多数市......
  • 一些sql笔记(sql sever)
    记录一些平日写sql的笔记insert语句INSERTINTO`table_name`(`column1`,`column2`,...)VALUES(`value1`,`value2`,...);update语句UPDATE`table_name`SET`column1`=`value1`,`column2`=`value2`,...WHERE`condition`;delete语句DELETEFROM......
  • 学习笔记-平衡树
    学习笔记-平衡树treap#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;#definelst[x].ch[0]#definerst[x].ch[1]constintN=114514;constintinf=2147483647;intcnt=0,root;mt19937rnd(0x7f);structtreap{ intch[2],cnt,size,val,......
  • DSP学习笔记
    DSP学习笔记之EPWMEPWM模块介绍F28335最多有18路PWM输出,其中有6个ePWM模块由两路ePWM输出组成,分为ePWMxA和ePWMxB,这一对PWM输出,可以配置成两路独立的单边沿PWM输出,或者两路独立的但互相相对称的双边沿PWM输出,或者一对双边沿非对称的PWM输出,因为每对PWM模块中的两个PWM......
  • 算法学习笔记(14):区间最值操作和历史最值问题
    区间最值操作,历史最值问题来源吉老师2016集训队论文,oiwiki,网络上各种博客。概述区间最值操作指的是:将所有的$i\in$\((l,r)\),\(a_i=min或max(a_i,k)\)。历史最值问题指的是:新定义一个数组\(b[]\),\(b[i]=max或min(b[i],a[i])\)。还有一种是历史版本和,即\(......
  • Docker安装笔记
    1、配置yum仓库(系统为Centos7)创建Centos基础镜像仓库,到阿里云镜像站https://developer.aliyun.com/mirror/找到Centos可以找到对应系统的镜像仓库。wget-O/etc/yum.repos.d/CentOS-Base.repohttps://mirrors.aliyun.com/repo/Centos-7.repo2、配置docker仓库创建Docker镜......
  • Python操作SAP时候遇到的一些常见问题
    1,每次使用程序去操作SAP时候,都会提示有脚本在AttachSAPGUI窗口A:可以修改在SAPGUIConfiguration中的设置,取消该提示 2,使用程序去操作SAP的时候,SAP无法找到Edit窗口,不会输入SAP系统A:可能是误点了下图的CommentField,这样会出现下面的Comment窗口。但是这个和填写S......
  • 一些运维技巧-抖音
    批量删除500万个文件rsync-av--deleteempty/demo/--exclude-from=exclude.txt#rsync快速通用的远程和本地文件复制工具#empty/源目录空目录,需要带/#demo/目标目录500万个文件目录,需要带/#--delete从目标目录中删除不在源目录的文件#--exclude-fr......
  • AI模型 Llama 3体验笔记
    4月19日Meta重磅推出了最新大型开源人工智能(AI)模型——Llama3,模型分为两种规模:8B和70B参数,旨在让个人、创作者、研究人员和各种规模的企业能够负责任地试验、创新和扩展他们的想法。  已经可以很方便的在本地部署、体验。Linux系统下安装脚本:curl-fsSLhttps://oll......