LeetCode算法心得——连续数组(前缀和+HashMap)

2023-09-21 17:42:25

大家好,我是晴天学长,公式的巧妙化简加上hashmap的灵活应用,需要的小伙伴可以关注支持一下哦!后续会继续更新的。


1) .连续数组

在这里插入图片描述

给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组,并返回该子数组的长度。

示例 1:

输入: nums = [0,1]
输出: 2
说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。
示例 2:

输入: nums = [0,1,0]
输出: 2
说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。


2) .算法思路

核心:由于以上碰1加一,碰0减一的操作,当0与1数量一致时(连续数组), 其连续数组的和为零。因此我们知道数组前面的 curcurcur 值是什么,在到达该连续数组尾部时就不会变。因此我们只需要检查哈希表中是否存在其相同的 curcurcur 值即可!(多读几遍)。

为什么在哈希表中找到了相同的 curcurcur 值则算找到了一串连续数组?
“如果这是一串连续子数组,那么cur的值,在到达该子数组尾部时(紫色箭头处),与在该子数组前一位时(绿色箭头处),是相等的” 。

在这里插入图片描述

为什么要在哈希表中插入{0, -1}? 这是为了辅助讨论该连续数组的起始点在 index == 0 的位置的情况,如果最长连续数组在数组的最前方,不插入{0,-1}会得到错误的答案,因此我们一定要插入该辅助键值!具体可以看看动图中的前几位数字看看{0,-1}是如何辅助我们得到答案的!


3) .算法步骤

连续数组
1.用hashmap统计每个下标 0 1 的数量
2.一段子数组的0和1的数量
s[R][1] - S[L][1] = S[R][0]-S[L][0];
S[R][1] - S[R][0] = S[L][1]-S[L][0];
3.遍历数组,找最大,所以存下标。
4.要是不存在就存下来,有就不存了,因为要找最大的子数组,肯定是L的最小,相减起来才是最大的。


4).代码示例

class Solution {
    public int findMaxLength(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
            int zero = 0;
            int one = 0;
            int maxindex = 0;
            map.put(0,-1);
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] == 0) {
                    zero++;
                } else {
                    one++;
                }
                int temp = one-zero;
                if (map.containsKey(temp)) {
                    if (maxindex < Math.abs((i - map.get(temp)))) {
                        maxindex = Math.abs((i - map.get(temp)));
                    }
                }
                else {
                    //没有再存
                    map.put(temp, i);
                }
            }
            return maxindex;
    }
}

5).总结

  • HashMap的应用。
  • 存下标。

试题链接:

更多推荐

BabelEdit 5.0.1 Crack

BabelEdit加强软件本地化。BabelEdit是处理json、yaml、php、arb、vue、properties、resx或xliff翻译文件的可靠解决方案。旨在使开发过程更加简化和高效。下载BabelEdit5.0.0对于Windows也适用于macOS和LinuxBabelEdit-适用于Web和应用程序

React核心概念

JSX基础语法在React中,使用JSX来描述页面。使用JSX来描述页面时,有如下的一些语法规则:根元素只能有一个JSX中使用JavaScript表达式。表达式在花括号{}内属性值指定为字符串字面量,或者在属性值插入一个JavaScript表达式style对应样式对象,class要写作className注释需要写在花括

gin 基本使用

gin初体验import("net/http""github.com/gin-gonic/gin")funcmain(){r:=gin.Default()r.GET("/ping",func(c*gin.Context){c.JSON(http.StatusOK,gin.H{"message":"pong",})})r

ESP32C3 PWM输出

目前对于遥控双发差速小飞机计划采用如下架构:ESP32C3做主控,兼具遥控收发和飞行控制锂电池供电,带电量检测双发,720空心杯电机,55mm桨,带电流检测MPU6050加速度计和陀螺仪预留4个控制信号输出马达控制要用到pwm,今天把esp32c3的pwm跑一下。简介esp32c3中把pwm外设称为“LEDPWM控制器

Qt重写QTreeWidget实现拖拽

介绍此文章记录QTreeWidget的重写进度,暂时停滞使用,重写了QTreeWidget的拖拽功能,和绘制功能,自定义了数据结构,增加复制,粘贴,删除,准备实现动态刷新数据支持千万数据动态刷新,重写了部分代码,重写了滑块拖拽但是有bug。效果展示实现功能实现了自定义节点类来存储数据。item采用Label来实现富文本

C++数据结构题:DS 顺序表--连续操作

建立顺序表的类,属性包括:数组、实际长度、最大长度(设定为1000)该类具有以下成员函数:构造函数:实现顺序表的初始化。插入多个数据的multiinsert(inti,intn,intitem[])函数,实现在第i个位置,连续插入来自数组item的n个数据,即从位置i开始插入多个数据。删除多个数据的multidel(i

JAVAEE初阶相关内容第十二弹--多线程(进阶)

目录一、JUC的常见类1、Callable接口1.1callable与runnable1.2代码实例(1)不使用Callable实现(2)使用Callable实现1.3理解Callable1.4理解FutureTask2、ReentrantLock2.1ReentrantLock的用法2.2ReentrantLock优

中科院预警名单

2023年预警名单(fenqubiao.com)如果论文投稿到中国科学院预警期刊,可能会面临以下情况:1.预警期刊一般审稿周期长,容易出现迟迟不见回音的情况。2.这类期刊的学术质量参差不齐,接受论文的学术标准可能不严格。3.预警期刊发表论文的学术影响力比较有限,不容易为作者带来高引用率和知名度。4.在中国的一些高校和科

新版考勤管理系统正式发布

O2OA(翱途)开发平台V8.1版本,因老的考勤管理系统已经无法满足用户需求,并且在架构和业务结构上都不再符合现在大多数考勤功能的需求。我们对考勤管理重新进行了开发,全新的版本更好用,更直观。考勤管理对员工的工作出勤情况进行记录、分析和报告的过程。它是对员工工作表现评估的重要依据,也是企业管理中的重要组成部分。考勤管理

多线程的学习上篇

座右铭:天行健,君子以自强不息;地势坤,君子以厚德载物.引入进程这个概念的目的引入进程这个概念,最主要的目的,是为了解决“并发编程"这样的问题.这是因为CPU进入了多核心的时代要想进一步提高程序的执行速度,就需要充分的利用CPU的多核资源其实,多进程编程,已经可以解决并发编程的问题了.已经可以利用起来CPU多核资源了.

【C++ 学习 ㉒】- 超详解 AVL 树的插入、平衡调整以及删除(含源代码)

目录一、AVL树的概念二、AVL树节点的定义三、AVL树的插入四、AVL树的平衡调整五、AVL树的删除六、AVL树的实现6.1-AVL.h6.2-test.cpp一、AVL树的概念二叉搜索树查找算法的性能取决于二叉树搜索树的形状,而二叉搜索树的形状则取决于数据集。如果数据呈有序排列,则二叉搜索树为单支树,查找的时间复杂

热文推荐