【Leetcode每日一题】 前缀和 - 连续数组(难度⭐⭐)(30)

news/2024/4/16 14:53:38/文章来源:https://blog.csdn.net/m0_73150338/article/details/136532229

1. 题目解析

题目链接:525. 连续数组

这个问题的理解其实相当简单,只需看一下示例,基本就能明白其含义了。

核心在于计算题目所给数组是否存在连续子数组使得数组里头0和1的数量相同,存在返回连续子数组最长长度即可,不存在返回0即可。

2.算法原理

稍微转化一下题目,我们可以将其转化为一个更熟悉的问题:

  • 本题要求找出一段连续的区间,使得其中0和1出现的次数相同。
  • 如果我们将0视为-1,1视为1,那么问题就转化为寻找一段区间,使得这段区间的和等于0。
  • 这个问题与“和为K的子数组”的思路相似,即通过前缀和和哈希表来寻找符合条件的子数组。

具体解题思路如下:

  1. 设定变量与数据结构
    • i为数组中的任意位置。
    • sum[i]表示从数组起始位置到位置i(包括i)之间所有元素(将0视为-1,1视为1)的和。
    • 使用一个哈希表来存储每个前缀和第一次出现的位置。
  2. 遍历数组并计算前缀和
    • 遍历数组,同时计算当前位置的前缀和sum[i]
    • 在遍历过程中,不断更新哈希表,记录每个前缀和第一次出现的位置。
  3. 查找符合条件的子数组
    • 对于每个位置i,检查哈希表中是否存在键为sum[i]的项。
    • 如果存在,说明在位置i之前存在一个位置x1,使得区间[x1, i]的和为0(即0和1的数量相同)。
    • 记录i - x1的值,这表示以i为结尾的符合条件的子数组的长度。
    • 更新最大长度(如果需要的话)。
  4. 注意事项
    • 不需要真正初始化一个完整的前缀和数组,因为只关心在位置i之前,前缀和等于sum[i]的位置。
    • 哈希表用于存储前缀和及其第一次出现的位置,这样可以在O(1)的时间内查找到符合条件的位置。

3.代码编写

class Solution 
{
public:int findMaxLength(vector<int>& nums) {unordered_map<int, int> hash;//前缀和和下标的关系hash[0] = -1;//默认前缀和为零时下标时-1int ret = 0, sum = 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;}
};

The Last

嗯,就是这样啦,文章到这里就结束啦,真心感谢你花时间来读。

觉得有点收获的话,不妨给我点个吧!

如果发现文章有啥漏洞或错误的地方,欢迎私信我或者在评论里提醒一声~ 

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

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

相关文章

pytest测试框架使用基础07 fixture—parametrize获取参数的几种常用形式

【pytest】parametrize获取参数的几种常用形式: a.数据结构 b.文件 c.数据库 d.conftest.py配置一、直接在标签上传参 1.1 一个参数多个值 pytest.mark.parametrize("参数", (参数值1, 参数值2, 参数值3))示例&#xff1a; import pytest # 单个参数的情况 pytest.…

Linux——MySQL主从复制与读写分离

实验环境 虚拟机 3台 centos7.9 网卡NAT模式 数量 1 组件包mysql-5.6.36.tar.gz cmake-2.8.6.tar.gz 设备 IP 备注 Centos01 192.168.223.123 Amoeba Centos02 192.168.223.124 Master Centos03 192.168.223.125 Slave MySQL安装 主从同时操作 安装所需要的…

安全特性 悬垂指针

英文名称 Dangling point&#xff0c;它还有一个兄弟叫 wild point - 野指针。 简单的对Dangling point做一个类比&#xff1a;我换手机号码了&#xff0c;但是没有通知老板&#xff0c;老板通讯录存的是我的旧号码。然后老板打电话有两种可能&#xff1a;打不通电话或者电话打…

华为od机试C卷-开源项目热度榜单

1、题目描述 某个开源社区希望将最近热度比较高的开源项目出一个榜单&#xff0c;推荐给社区里面的开发者。 对于每个开源项目&#xff0c;开发者可以进行关注(watch)、收藏(star)、fork、提issue、提交合并请求(MR)等。 数据库里面统计了每个开源项目关注、收藏、fork、issue…

关于进程和线程

目录 前言: 1进程: 1.1定义&#xff1a; 1.1.1进程是操作系统分配资源的基本单元&#xff0c;拥有自己的独立空间和资源。 1.1.2每个进程都有一个唯一的PID&#xff08;进程标识符&#xff09;来标识。 1.2进程间通信&#xff1a; 1.2.1进程不是孤立的&#xff0c;它们之…

快速搭建Vue前端框架

快速搭建Vue前端框架 安装Vue Vue官方安装过程:https://cli.vuejs.org/zh/guide/installation.html 二.创建Vue工程 2.2 安装淘宝镜像 安装淘宝镜像&#xff08;会让你安装Vue的速度加快&#xff09;&#xff1a; npm config set registry https://registry.npm.taobao.or…

视频生成模型Sora的全面解析:从AI绘画、ViT到ViViT、DiT、VDT、NaViT、VideoPoet

视频生成模型Sora的全面解析&#xff1a;从AI绘画、ViT到ViViT、DiT、VDT、NaViT、VideoPoet 真没想到&#xff0c;举例视频生成上一轮的集中爆发才过去三个月&#xff0c;没想OpenAI一出手&#xff0c;该领域又直接变天了自打2.16日OpenAI发布sora以来&#xff0c;不但把同时…

经典定时任务结构设计:时间轮(Timing Wheel)案例和实现原理

1、直接上案例 import io.netty.util.HashedWheelTimer; import io.netty.util.Timeout; import io.netty.util.TimerTask; import lombok.extern.log4j.Log4j2;import java.util.concurrent.TimeUnit;/*** ClassName Test* Author will* Date 2024/3/8 16:31* Version 1.0.1*…

【Spring面试题】

目录 前言 1.Spring框架中的单例bean是线程安全的吗? 2.什么是AOP? 3.你们项目中有没有使用到AOP&#xff1f; 4.Spring中的事务是如何实现的&#xff1f; 5.Spring中事务失效的场景有哪些&#xff1f; 6.Spring的bean的生命周期。 7.Spring中的循环引用 8.构造方法…

STM32F4串口波特率相关时钟

在main中调用的 Stm32_Clock_Init(336, 8, 2, 7); /* 设置时钟,168Mhz *///8*336/8/2168 时钟源,PLL寄存器配置函数: HAL_StatusTypeDef HAL_RCC_OscConfig(RCC_OscInitTypeDef *RCC_OscInitStruct) 系统时钟,总线寄存器配置,及HCLK时钟计算函数: HAL_StatusTyp…

finishConnect(..) failed: Connection refused,服务本地正常服务器网关报400,nacos服务实例不能下线

①application里固定ip # Spring spring:cloud:inetutils:preferred-networks: 127.0.0.1 ②找到nacos服务下的protocol&#xff0c;删除下面所有&#xff0c;/nacos-server/data/protocol&#xff0c;删了不会有问题&#xff0c;而且这东西越用越大&#xff0c;删了好爽 ③重…

Platformview在iOS与Android上的实现方式对比

Android中早期版本Platformview的实现基于Virtual Display。VirtualDisplay方案的原理是&#xff0c;先将Native View绘制到虚显&#xff0c;然后Flutter通过从虚显输出中获取纹理并将其与自己内部的widget树进行合成&#xff0c;最后作为Flutter在 Android 上更大的纹理输出的…

电脑安装原版Windows7详细教程

前言 截止2024年3月3日&#xff0c;仍然有不少小伙伴想给电脑安装Windows7。所以今天给小伙伴们出一篇电脑安装原版Windows7的详细教程。 首先要知道部分CPU&#xff08;第六代或以上英特尔、AMD Ryzen系列&#xff09;平台并不支持Windows7&#xff0c;原因是有部分硬件设备…

阿里云DSW做AI绘画时的显卡选择A10?V100?

V100是Volta架构&#xff0c;A10是Ampere架构&#xff0c;架构上讲A10先进点&#xff0c;其实只是制程区别&#xff0c;用起来没区别。 V100是HBM的内存读取&#xff0c;带宽大&#xff0c;但是DDR5的。 二块卡都是全精度为主的算力卡&#xff0c;半精度优势不明显。 需要用…

力扣每日一题 找出字符串的可整除数组 数论

Problem: 2575. 找出字符串的可整除数组 文章目录 思路复杂度Code 思路 &#x1f468;‍&#x1f3eb; 灵神题解 复杂度 时间复杂度: O ( n ) O(n) O(n) 空间复杂度: O ( 1 ) O(1) O(1) Code class Solution {public int[] divisibilityArray(String word, int m){in…

测试常用的Linux命令

前言 直接操作硬件 将把操作硬件的代码封装成系统调用&#xff0c;供程序员使用 虚拟机软件 可以模拟的具有完整硬件系统的功能 可以在虚拟机上安装不同的操作系统 Linux内核只有一个&#xff0c;发行版有很多种 内核来运行程序和管理像磁盘和打印机等硬件设备的核心程序 终端…

python 基础知识点(蓝桥杯python科目个人复习计划59)

今日复习内容&#xff1a;做题 例题1&#xff1a;建造房屋 问题描述&#xff1a; 小蓝和小桥是两位年轻的建筑师&#xff0c;他们正在设计一座新的城市。 在这个城市中&#xff0c;有N条街道&#xff0c;每条街道上有M个位置可以建造房屋&#xff08;一个位置只能建造一个房…

测试面试精选题:可用性测试主要测试哪些方面,举例说明

1.界面设计&#xff1a; 评估软件的用户界面设计是否直观、美观、易于理解和操作。 测试用例&#xff1a;打开软件&#xff0c;查看界面布局是否合理&#xff0c;各个功能是否容易找到&#xff0c;是否符合用户习惯。 2.导航和布局&#xff1a; 评估用户在软件中导航和查找…

python 爬虫爬取知乎LOL图片(亲测)

获取信息 访问url后按f12调试 点击network 定位图片信息&#xff1a; 可以看到&#xff0c;每个图片的名字和下载地址在标红处&#xff0c;示例如下&#xff1a; data-actualsrc“https://pic4.zhimg.com/v2-1681ff26afbd5f92aa5790b4dee6a63f_b.jpg” 现在就是requests访问…

数据结构(一)——概述

一、绪论 1.1数据结构的基本概念 数据&#xff1a;用来描述客观事物的数、计算机中是字符及所有能输入并被程序识别和处理的符号的集合。 数据元素&#xff1a;数据的基本单位&#xff0c;一个数据元素可由若干数据项组成。 数据结构&#xff1a;指相互之间存在一种或多种特…