力扣精选算法100道—— 连续数组(前缀和专题)

连续数组(前缀和专题)

目录

🚩了解题意

🚩算法原理

❗为什么hash设置成<0,-1>键值对

❗与和为K的子数组比较hash的键值对

🚩代码实现


🚩了解题意

我们看到给定数组里面只有0和1,我们要找到一个连续的子数组具有相同数量的0和1,那么我们想想,如果我们给0代替成-1,那么-1 1 -1 1是不是等于0是不是相当于找到了具有相同数量的0和1了。

所以 我们首先要想到 将0改成-1 ,然后找到相同的0和1的数量就转换成在数组中最长的子数组中和为0.

这一题和 和为K的子数组 很像 ——和为0的子数组(我们只需要将0改成-1即可)


🚩算法原理

该函数的主要目的是找到nums中的一个最长的连续子数组,该子数组中0和1的数量相等。它使用了一个哈希表hash来记录当前累积和首次出现的位置,以便在后续遍历中可以计算当前累积和与首次出现位置之间的距离,从而得到最长的满足条件的子数组长度。

还是利用哈希+前缀和思路。但是这一题我们需要考虑到几个细节。

我们先给过程分析一下吧

  1. 创建一个无序哈希表hash,用于存储累积和及其首次出现的位置。初始化时将累积和为0的位置设为-1,这样方便后续计算。
  2. 初始化两个整数变量sumret,分别用于存储当前累积和和最长满足条件的子数组长度。
  3. 使用循环遍历nums中的每个元素,对累积和进行更新。如果当前元素为0,则累积和加上-1,否则加上1。
  4. 在每次更新累积和后,检查哈希表中是否已经记录了当前累积和。如果已经记录,则计算当前位置与首次出现位置的距离,并更新最长子数组长度ret。否则,将当前累积和及其位置记录到哈希表中。
  5. 最后,返回最长子数组长度ret作为结果。

这段代码的时间复杂度为O(n),其中n是输入向量nums的长度。


这里有几个细节问题

为什么累积和为0的位置设为-1,我们根据一个情况来阐述吧

<0,-1>键值对,0代表前缀和,-1代表下标。

❗为什么hash设置成<0,-1>键值对

在这段代码中,将累积和为0的位置设为-1的目的是为了在计算最长子数组长度时能够正确处理从数组开头开始的子数组。

在遍历数组时,累积和为0意味着从数组开始到当前位置的子数组中0和1的数量相等。因此,如果在后续的遍历中再次遇到累积和为0,那么说明中间这段子数组中0和1的数量仍然相等。

如果没有将累积和为0的位置设为-1,而是设为0,那么在计算距离时可能会得到错误的结果。因为累积和为0的情况可能出现在数组的第一个位置,此时距离为当前位置减去0,会导致计算出的距离比实际子数组长度小1。

因此,将累积和为0的位置设为-1可以避免这种情况,确保计算出的最长子数组长度是正确的。


❗与和为K的子数组比较hash的键值对

hash[0] = 1 的目的是在处理前缀和时确保能够正确统计到和为k的子数组的数量。这是一个常用的技巧,主要是为了处理当前缀和恰好等于k的情况。

具体来说,hash 这个哈希表用于统计前缀和出现的次数。在初始化时,将累积和为0的次数设置为1是为了确保能够正确处理累积和等于k的情况。

考虑这样一种情况,如果数组中存在一个子数组的和正好等于k,那么这个子数组的前缀和减去k就等于0。因此,在遍历数组时,当遇到一个前缀和sum时,如果之前已经有一个前缀和sum - k存在,那么说明从那个前缀和到当前位置的子数组和正好为k。

举个例子,假设有数组 nums = [1, 2, 3],而 k = 3。在遍历过程中,前缀和依次为1、3、6,此时对于前缀和为3,前缀和为0的情况正好存在,这意味着从数组开头到当前位置的子数组和为3,满足条件。

因此,初始化时将 hash[0] = 1 是为了确保能够正确处理这种情况。


和为K的子数组:<0,1> 在和为K的子数组中0代表前缀和,1代表前缀和出现的次数

和为0的子数组:这一题<0,-1> 在和为0的子数组中 0代表前缀和,-1代表下标的位置。


🚩代码实现

class Solution {
public:int findMaxLength(vector<int>& nums) {unordered_map<int,int>hash;hash[0]=-1;int sum=0,ret=0;int dest=0;for(int i=0;i<nums.size();i++){sum+=nums[i]==0?-1:1;//如果sums[i]==0就改成-1,否则就是1if(hash.count(sum)) ret=max(ret,i-hash[sum]);else hash[sum]=i;//这里记录的是长度}return ret;}
};

我们会一直一直在一起哒!

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

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

高斯伪谱C++封装库开源!

Windows x64/86 C无依赖运行高斯伪谱法求解最优控制问题&#xff0c;你只需要ElegantGP! Author: Y. F. Zhang His Github: https://github.com/ZYunfeii 写在前面 这个库在你下载它的那一时刻起不再依赖任何其他代码&#xff0c;直接可用来构建C的最优控制问题并进行求解。…

[C/C++] -- CMake使用

CMake&#xff08;Cross-platform Make&#xff09;是一个开源的跨平台构建工具&#xff0c;用于自动生成用于不同操作系统和编译器的构建脚本。它可以简化项目的构建过程&#xff0c;使得开发人员能够更方便地管理代码、依赖项和构建设置。 CMake 使用一个名为 CMakeLists.tx…

微服务入门篇:Nacos注册中心(Nacos安装,快速入门,多级存储,负载均衡,环境隔离,配置管理,热更新,集群搭建,nginx反向代理)

目录 1.Nacos安装1.官网下载2.解压到本地3.启动nacos 2.Nacos快速入门1.在父工程中导入nacos依赖2.给子项目添加客户端依赖3.修改对应服务的配置文件4.启动服务&#xff0c;查看nacos发现情况 3.Nacos服务多级存储模型4.NacosRule负载均衡5. 服务实例的权重设置6.环境隔离&…

双重OSPF + OSPF综合实验

一、实验要求 1.R4为ISP&#xff0c;所连接的所有物理接口为公有网段&#xff0c;任意指定IP即可。 2.R1-2-3 构建一个星型结构的MGRE结构&#xff0c;其中R1为中心点&#xff0c;假设R1的公有IP为固定地址。 3.R1-5-6 构建另一个全连网状的MGRE网络&#xff0c;其中R1/5均为中…

网络套件字(理论知识)

一、源IP地址和目的IP地址 上次说到IP地址是为了是为了让信息正确的从原主机传送到目的主机&#xff0c;而原IP地址和目的IP地址就是用于标识两个主机的&#xff0c;既然叫做地址必然有着路径规划的作用&#xff0c;而路径规划最重要的就是&#xff0c;从哪来到哪去&#xff0…

计算机网络基本知识(二)

文章目录 概要分层为什么分层怎么分层&#xff1f;1.实体2.协议3.服务 分层基本原则正式认识分层详细例子解释 总结 概要 分层知识&#xff1a;概念理解 分层 为什么分层 大致以上五点 为了解决上面的问题&#xff08;复杂&#xff09; 大问题划分为小问题 怎么分层&#…

新手小白做steam搬砖项目,这些内幕要了解

转眼2024年已经过去了五分之一&#xff0c;很多粉丝都在问steam搬砖项目真的假的&#xff0c;害怕项目的风险&#xff0c;担心steam搬砖项目到底能不能做&#xff0c;所以一直在犹豫和徘徊。我发现很多人想赚钱&#xff0c;但苦于找不到好的副业&#xff0c;高门槛的项目又做不…

C语言的循环结构

目录 前言 1.三种循环语句 1.while循环 2.for循环 2.1缺少表达式的情况 3.do while循环 2.break语句和continue语句 2.1在while循环中 2.2在for循环中 2.3在do while 循环中 3.循环的嵌套 4.go to语句 前言 C语⾔是结构化的程序设计语⾔&#xff0c;这⾥的结构指的是…

【机器学习】数据清洗之识别缺失点

&#x1f388;个人主页&#xff1a;甜美的江 &#x1f389;欢迎 &#x1f44d;点赞✍评论⭐收藏 &#x1f917;收录专栏&#xff1a;机器学习 &#x1f91d;希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出指正&#xff0c;让我们共同学习、交流进步…

Verilog刷题笔记23

题目: Suppose you’re building a circuit to process scancodes from a PS/2 keyboard for a game. Given the last two bytes of scancodes received, you need to indicate whether one of the arrow keys on the keyboard have been pressed. This involves a fairly simp…

【LeetCode】51. N 皇后(困难)——代码随想录算法训练营Day30

题目链接&#xff1a;51. N 皇后 题目描述 按照国际象棋的规则&#xff0c;皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 n 皇后问题 研究的是如何将 n 个皇后放置在 nn 的棋盘上&#xff0c;并且使皇后彼此之间不能相互攻击。 给你一个整数 n &#xff0c;返回…

day34 本地存储(重要)

目录 本地存储简介本地存储分类—— localStorage本地存储分类—— sessionStorage&#xff08;了解&#xff09;存储复杂数据类型问题1&#xff1a;本地只能存储字符串,无法存储复杂数据类型。问题2&#xff1a;因为本地存储里面取出来的是字符串&#xff0c;不是对象&#xf…

react将选中文本自动滑动到容器可视区域内

// 自动滚动到可视区域内useEffect(() > {const target ref;const wrapper wrapperRef?.current;if (target && wrapperRef) {const rect target.getBoundingClientRect();const wrapperRect wrapper.getBoundingClientRect();const isVisible rect.bottom &l…

消息队列MQ 介绍

&#x1f47d;System.out.println(“&#x1f44b;&#x1f3fc;嗨&#xff0c;大家好&#xff0c;我是代码不会敲的小符&#xff0c;双非大四&#xff0c;Java实习中…”); &#x1f4da;System.out.println(“&#x1f388;如果文章中有错误的地方&#xff0c;恳请大家指正&a…

掌握虚拟化与网络配置之道:深入浅出VMware及远程管理技巧

目录 虚拟机介绍 虚拟机的关键字 服务器架构的发展 为什么用虚拟机VMware 虚拟机和阿里云的区别 功能角度 价格因素 应用场景 优势方面 找到windows的服务管理 配置VMware 关于VMware安装的几个服务 vmware如何修改各种网络配置 关于NAT的详细信息(了解) NAT(网…

我的docker随笔43:问答平台answer部署

本文介绍开源问答社区平台Answer的容器化部署。 起因 笔者一直想搭建一个类似stack overflower这样的平台&#xff0c;自使用了Typora&#xff0c;就正式全面用MarkdownTyporagit来积累自己的个人知识库&#xff0c;但没有做到web化&#xff0c;现在也还在探索更好的方法。 无…

常见的ANSI转义码

ANSI 转义码是一组控制码&#xff0c;用于在文本中添加格式化和颜色。这些码以 ESC&#xff08;Escape&#xff09;字符为开头&#xff0c;通常是 \x1b&#xff0c;后面紧跟着一系列参数和指令。在 ANSI 标准中&#xff0c;这些码通常用于控制终端的文本输出。 下面是一些常见…

springboo冬奥会科普平台源码和论文

随着信息技术和网络技术的飞速发展&#xff0c;人类已进入全新信息化时代&#xff0c;传统管理技术已无法高效&#xff0c;便捷地管理信息。为了迎合时代需求&#xff0c;优化管理效率&#xff0c;各种各样的管理平台应运而生&#xff0c;各行各业相继进入信息管理时代&#xf…

cocos creator 3.x 预制体无法显示

双击预制体&#xff0c;进入详情页&#xff0c;没有显示资源 Bomb 是个预制体&#xff0c;但是当我双击进来什么都没有了&#xff0c;无法对预制体进行可视化编辑 目前我只试出来一个解决方法&#xff1a; 把预制体拖进Canvas文件中&#xff0c;这样就能展示到屏幕上&#xff…

为什么要设置止损

2024年1月至2月7日&#xff0c;A股最令人瞩目的事件就是代表小微盘的中证500和中证1000雪球连续敲入&#xff0c;以及万得微盘指数的崩塌&#xff08;1个月下跌50%&#xff09;。 这次的这个过程中&#xff0c;止损很重要。一般情况下&#xff0c;如果设置了20%回撤止损的话&am…