力扣精选算法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来记录当前累积和首次出现的位置,以便在后续遍历中可以计算当前累积和与首次出现位置之间的距离,从而得到最长的满足条件的子数组长度。
还是利用哈希+前缀和思路。但是这一题我们需要考虑到几个细节。
我们先给过程分析一下吧

- 创建一个无序哈希表
hash,用于存储累积和及其首次出现的位置。初始化时将累积和为0的位置设为-1,这样方便后续计算。 - 初始化两个整数变量
sum和ret,分别用于存储当前累积和和最长满足条件的子数组长度。 - 使用循环遍历
nums中的每个元素,对累积和进行更新。如果当前元素为0,则累积和加上-1,否则加上1。 - 在每次更新累积和后,检查哈希表中是否已经记录了当前累积和。如果已经记录,则计算当前位置与首次出现位置的距离,并更新最长子数组长度
ret。否则,将当前累积和及其位置记录到哈希表中。 - 最后,返回最长子数组长度
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;}
};
我们会一直一直在一起哒!
相关文章:
力扣精选算法100道—— 连续数组(前缀和专题)
连续数组(前缀和专题) 目录 🚩了解题意 🚩算法原理 ❗为什么hash设置成<0,-1>键值对 ❗与和为K的子数组比较hash的键值对 🚩代码实现 🚩了解题意 我们看到给定数组里面只有0和1,我们…...
flutter 国内源
Flutter 在中国由于网络原因,从官方默认的国外源下载Dart包和Flutter SDK可能会比较慢或者不稳定。为了加速依赖包的获取与Flutter SDK的安装,可以使用国内镜像源。以下是一些国内常用的Flutter和Dart包镜像源: 清华大学开源软件镜像站 Flu…...
第九个知识点:内部对象
Date对象: <script>var date new Date();date.getFullYear();//年date.getMonth();//月date.getDate();//日date.getDay();//星期几date.getHours();//时date.getMinutes();//分date.getSeconds();//秒date.getTime();//获取时间戳,时间戳时全球统一&#x…...
Android 车载应用开发之车载操作系统
一、前言 到 2030 年,全球电动汽车的销量将超过 7000 万辆,保有量将达到 3.8 亿辆,全球年度新车渗透率有望触及 60% 。这一数据来自国际能源署(IEA)发布的《全球电动汽车展望2023》。 市场趋势和政策努力的双加持下,新能源汽车来势凶猛,燃油车保有量逐年递减。此番景象…...
Qt PCL学习(文章链接汇总)
Qt PCL学习(一):环境搭建 Qt PCL学习(二):点云读取与保存 Qt PCL学习(三):点云滤波 Qt PCL学习(四):点云关键点 持续更新中…...
安卓动态链接库文件体积优化探索实践
背景介绍 应用安装包的体积影响着用户下载量、安装时长、用户磁盘占用量等多个方面,据Google Play统计,应用体积每增加6MB,安装的转化率将下降1%。 安装包的体积受诸多方面影响,针对dex、资源文件、so文件都有不同的优化策略&…...
[Java][算法 哈希]Day 01---LeetCode 热题 100---01~03
LeetCode 热题 100---01~03 ------->哈希 第一题 两数之和 思路 最直接的理解就是 找出两个数的和等于目标数 这两个数可以相同 但是不能是同一个数字(从数组上理解就是内存上不是同一位置) 解法一:暴力法 暴力解万物 按照需求 …...
【每日一题】LeetCode——链表的中间结点
📚博客主页:爱敲代码的小杨. ✨专栏:《Java SE语法》 | 《数据结构与算法》 | 《C生万物》 ❤️感谢大家点赞👍🏻收藏⭐评论✍🏻,您的三连就是我持续更新的动力❤️ 🙏小杨水平有…...
k8s 部署java应用 基于ingress+jar包
k8 集群ingress的访问模式 先部署一个namespace 命名空间 vim namespace.yaml kind: Namespace apiVersion: v1 metadata:name: ingress-testlabels:env: ingress-test 在部署deployment deployment是pod层一层封装。可以实现多节点部署 资源分配 回滚部署等方式。 部署的…...
深度学习技巧应用36-深度学习模型训练中的超参数调优指南大全,总结相关问题与答案
大家好,我是微学AI,今天给大家介绍一下深度学习技巧应用36-深度学习模型训练中的超参数调优指南大全,总结相关问题与答案。深度学习模型训练中的调优指南大全概括了数据预处理、模型架构设计、超参数优化、正则化策略和训练技巧等多个关键方面,以提升模型性能和泛化能力。 …...
“探索AJAX:前端与后端数据交互的利器“
前言 在现代Web开发中,前端与后端之间的数据交互是一个至关重要的环节。为了实现无需刷新页面的动态更新,AJAX(Asynchronous JavaScript and XML)作为一种强大的技术被广泛应用。 AJAX的原理 AJAX通过JavaScript和XMLHttpReque…...
【5G NR】移动通讯中使用的信道编解码技术
目录 一、引言 二、信道编解码技术概述 三、移动通讯中常用的信道编解码技术 四、优缺点分析与比较 五、未来发展趋势 六、结论 本文主要介绍了移动通讯中采用的信道编解码技术,由于在5G NR终端中,通常要兼容4G LTE通讯技术,所以4G LTE…...
用Python Tkinter打造的精彩连连看小游戏【附源码】
文章目录 连连看小游戏:用Python Tkinter打造的精彩游戏体验游戏简介技术背景MainWindow类:职责:方法:Point类: 主执行部分:完整代码:总结: 连连看小游戏:用Python Tkinter打造的精彩游戏体验 在丰富多彩的游戏世界中,…...
nvm安装node后,npm无效
类似报这种问题,是因为去github下载npm时下载失败, Please visit https://github.com/npm/cli/releases/tag/v6.14.17 to download npm. 第一种方法:需要复制这里面的地址爬梯子去下载(github有时不用梯子能直接下载,有…...
spring boot(2.4.x 开始)和spring cloud项目中配置文件application和bootstrap加载顺序
在前面的文章基础上 https://blog.csdn.net/zlpzlpzyd/article/details/136060312 spring boot 2.4.x 版本之前通过 ConfigFileApplicationListener 加载配置 https://github.com/spring-projects/spring-boot/blob/v2.3.12.RELEASE/spring-boot-project/spring-boot/src/mai…...
5-2、S曲线计算【51单片机+L298N步进电机系列教程】
↑↑↑点击上方【目录】,查看本系列全部文章 摘要:本节介绍S曲线的基本变换,将基本形式的S曲线变换成为任意过两点的S曲线,为后续步进电机S曲线运动提供理论支撑 一.计算目标 ①计算经过任意不同两点的S曲线方程 ②可调节曲线平…...
SQL 注入 - http头注入之UA头注入探测
环境准备:构建完善的安全渗透测试环境:推荐工具、资源和下载链接_渗透测试靶机下载-CSDN博客 一、http头注入介绍 HTTP头注入是一种网络安全攻击手段,它利用了Web应用程序对HTTP头的处理不当或缺乏充分的验证和过滤。在这种攻击中,攻击者通过修改HTTP请求头中的某些字段,…...
学习数据结构和算法的第5天
空间复杂度及其常见案例 空间复杂度 空间复杂度也是一个数学函数表达式,是对一个算法在运行过程中临时占用存储空间大小的量度。 空间复杂度不是程序占用了多少bytes的空间,因为这个也没太大意义,所以空间复杂度算的是变量的个数。空间复杂度…...
Android 11 访问 Android/data/或者getExternalCacheDir() root方式
前言: 需求要求安装三方应用ExternalCacheDir()下载下来的apk文件。 getExternalCacheDir() : /storage/emulated/0/Android/data/com../cache/ 获取访问权限 如果手机安卓版本为Android10的时候,可以在AndroidManifest.xml中添加下列代码 android:requestLegacyExt…...
Linux探秘之旅:透彻理解路径、命令与系统概念
目录 如何远程连接 远程登录简明指南 linux区别 1.严格区分大小写 2.linux的命令返回结果判断 3.如何查看网络信息 4.关于后缀名(Linux不关心文件后缀) 4.1 需要记忆的后缀 5.echo命令 6.linux一切皆文件 6.1比如磁盘的文件 6.2可执行文件 …...
(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)
题目:3442. 奇偶频次间的最大差值 I 思路 :哈希,时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况,哈希表这里用数组即可实现。 C版本: class Solution { public:int maxDifference(string s) {int a[26]…...
第19节 Node.js Express 框架
Express 是一个为Node.js设计的web开发框架,它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用,和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...
深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录
ASP.NET Core 是一个跨平台的开源框架,用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录,以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...
React 第五十五节 Router 中 useAsyncError的使用详解
前言 useAsyncError 是 React Router v6.4 引入的一个钩子,用于处理异步操作(如数据加载)中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误:捕获在 loader 或 action 中发生的异步错误替…...
Cursor实现用excel数据填充word模版的方法
cursor主页:https://www.cursor.com/ 任务目标:把excel格式的数据里的单元格,按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例,…...
【位运算】消失的两个数字(hard)
消失的两个数字(hard) 题⽬描述:解法(位运算):Java 算法代码:更简便代码 题⽬链接:⾯试题 17.19. 消失的两个数字 题⽬描述: 给定⼀个数组,包含从 1 到 N 所有…...
【JVM】- 内存结构
引言 JVM:Java Virtual Machine 定义:Java虚拟机,Java二进制字节码的运行环境好处: 一次编写,到处运行自动内存管理,垃圾回收的功能数组下标越界检查(会抛异常,不会覆盖到其他代码…...
基于Uniapp开发HarmonyOS 5.0旅游应用技术实践
一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架,支持"一次开发,多端部署",可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务,为旅游应用带来…...
MODBUS TCP转CANopen 技术赋能高效协同作业
在现代工业自动化领域,MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步,这两种通讯协议也正在被逐步融合,形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...
selenium学习实战【Python爬虫】
selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...
