当前位置: 首页 > news >正文

【LeetCode Hot100 哈希】两数之和、字母异位词分组、最长连续序列

哈希

    • 1. 两数之和
      • 题目描述
      • 解题思路
        • 步骤:
        • 时间复杂度:
        • 空间复杂度:
      • 代码实现
    • 2. 字母异位词分组
      • 题目描述
      • 解题思路
        • 步骤:
        • 时间复杂度:
        • 空间复杂度:
      • 代码实现
    • 3. 最长连续序列
      • 题目描述
      • 解题思路
        • 关键思路:
        • 步骤:
        • 时间复杂度:
        • 空间复杂度:
      • 代码实现

1. 两数之和

题目描述

给定一个整数数组 nums 和一个目标值 target,在数组中找出两个数字,使它们的和为目标值 target。你需要返回这两个数字的下标。

注意:

  • 你可以假设每个输入只会有一个答案,并且你可以按任意顺序返回答案。
  • 不允许使用循环外的额外空间,且时间复杂度必须是 O(n)。

解题思路

为了高效地找到目标值 target 的两个数字,采用了哈希表来存储遍历过程中遇到的数字及其对应的索引。

步骤:
  1. 初始化哈希表:
    我们使用一个哈希表 hashTable 来存储数组 nums 中每个数字及其对应的索引。哈希表的 key 为数字,value 为该数字在数组中的索引。

  2. 遍历数组:
    我们遍历数组 nums,对于每个元素 nums[i],检查哈希表中是否存在一个元素,使得 nums[i] 和该元素的和为 target
    具体来说,我们检查哈希表中是否包含 target - nums[i]。如果存在,说明我们找到了两个数字,它们的和为 target,返回它们的下标。

  3. 更新哈希表:
    如果当前数字 nums[i] 与之前的数字不能组成目标和,则将 nums[i] 和它的下标 i 存入哈希表,继续查找。

  4. 返回结果:
    如果找到了满足条件的两个数字,就返回它们的下标;如果遍历结束后仍未找到,则返回空数组。

时间复杂度:
  • 遍历一次数组,查找哈希表的操作时间复杂度为 O(1),因此总的时间复杂度为 O(n),其中 n 为数组的长度。
空间复杂度:
  • 我们使用了一个哈希表来存储数组元素和其下标,哈希表的大小最多为数组的长度,因此空间复杂度为 O(n)。

代码实现

class Solution {public int[] twoSum(int[] nums, int target) {// 使用hashMap<Integer, Integer> hashTable = new HashMap<Integer, Integer>();for(int i = 0; i < nums.length; i++) {// 检查 target - nums[i] 是否在哈希表中if(hashTable.containsKey(target - nums[i])){return new int[]{hashTable.get(target - nums[i]), i};}// 将当前数字和其下标放入哈希表hashTable.put(nums[i], i);  }return new int[0];  // 如果没有找到,返回空数组}
}

2. 字母异位词分组

题目描述

给定一个字符串数组 strs,将字符串按字母异位词(Anagram)进行分组。字母异位词是指两个字符串中包含的字符完全相同,且字符的顺序不同。

例如,"eat""tea",和 "ate" 是字母异位词。要求将这些字母异位词分到同一组中。

注意:

  • 输入的字符串只包含小写字母。
  • 需要将所有字母异位词按顺序返回。

解题思路

为了将字母异位词分组,我们可以利用字符串的字母排序特性:对于字母异位词,它们的排序结果是相同的。我们可以通过对字符串进行排序,将字母异位词映射到相同的键上,进而将它们分到同一组。

步骤:
  1. 定义哈希表:
    使用一个哈希表 map,其键是排序后的字符串,值是一个包含所有字母异位词的列表。

  2. 遍历字符串数组:
    对于每个字符串,将其转化为字符数组并进行排序,得到一个排序后的字符串。这个排序后的字符串作为哈希表的键。

  3. 存入哈希表:
    查找哈希表中是否已经存在该键。如果存在,就将该字符串加入对应的列表;如果不存在,则在哈希表中创建一个新的列表并添加该字符串。

  4. 返回结果:
    最后,哈希表中存储了所有的字母异位词分组,直接返回哈希表的所有值。

时间复杂度:
  • 对于每个字符串,我们将其转化为字符数组并进行排序,排序的时间复杂度为 O(m log m),其中 m 是字符串的长度。
  • 遍历字符串数组的时间复杂度为 O(n),其中 n 是字符串数组的长度。
  • 因此,总的时间复杂度为 O(n * m log m),其中 n 是字符串数组的长度,m 是字符串的平均长度。
空间复杂度:
  • 哈希表存储了所有的字符串及其对应的字母异位词,因此空间复杂度为 O(n * m),其中 n 是字符串数组的长度,m 是字符串的平均长度。

代码实现

class Solution {public List<List<String>> groupAnagrams(String[] strs) {Map<String, List<String>> map = new HashMap<>();for (String str : strs) {// 将字符串转换为字符数组并排序char[] strArray = str.toCharArray();Arrays.sort(strArray);// 使用排序后的字符串作为键String key = new String(strArray); // 获取或创建该键的对应列表List<String> list =  map.getOrDefault(key, new ArrayList<String>());// 将当前字符串添加到列表中list.add(str);// 更新哈希表中的列表map.put(key, list);}// 返回哈希表的所有值,即字母异位词分组return new ArrayList<List<String>>(map.values());}
}

3. 最长连续序列

题目描述

给定一个无序的整数数组 nums,返回其中最长的连续元素序列的长度。

要求:你必须设计时间复杂度为 O(n) 的算法解决此问题。

解题思路

该题要求我们找到一个无序数组中的最长连续子序列。为了满足 O(n) 的时间复杂度,不能采用排序的方式,因为排序的时间复杂度为 O(n log n)。我们可以使用哈希集合(Set)来解决这个问题。

关键思路:
  1. 使用哈希集合存储数组元素:
    将数组中的每个元素加入哈希集合中,能够在 O(1) 的时间内判断某个元素是否存在。

  2. 只从连续序列的第一个元素开始搜索:
    遍历集合时,对于每个数字 num,我们只在 num-1 不在集合中的时候开始查找连续序列的长度。这样做可以避免重复计算(例如,当处理到序列中的中间元素时,已经遍历过它前面的元素)。

  3. 扩展连续序列:
    对于每个有效的起点 num,我们尝试通过 num+1num+2 等,找到该序列的最大长度。

  4. 更新结果:
    每次找到一个新的序列,更新当前最长的连续序列的长度。

步骤:
  1. 将数组元素加入哈希集合 set 中。
  2. 遍历集合,对于每个元素 num
    • 如果 num-1 不在集合中,说明 num 是某个连续序列的起点。
    • 向右扩展,检查 num+1 是否在集合中,直到不再连续为止。
    • 更新最长连续序列的长度。
时间复杂度:
  • 将所有元素加入集合需要 O(n) 时间。
  • 遍历数组时,每个元素最多会被处理一次,因此总的时间复杂度为 O(n)。
空间复杂度:
  • 哈希集合存储了所有数组元素,因此空间复杂度为 O(n)。

代码实现

class Solution {public int longestConsecutive(int[] nums) {// 使用哈希集合存储数组元素Set<Integer> set = new HashSet<>();for (int num : nums) {set.add(num);}int longest = 0;// 遍历数组中的每个元素for (int num : set) {// 如果 num-1 不在集合中,说明 num 是一个连续序列的起点if (!set.contains(num - 1)) {int currentNum = num;int currentLong = 1;// 向右扩展,寻找连续的数字while (set.contains(currentNum + 1)) {currentLong++;currentNum++;}// 更新最长连续子序列的长度longest = Math.max(longest, currentLong);}}return longest;}
}

相关文章:

【LeetCode Hot100 哈希】两数之和、字母异位词分组、最长连续序列

哈希 1. 两数之和题目描述解题思路步骤&#xff1a;时间复杂度&#xff1a;空间复杂度&#xff1a; 代码实现 2. 字母异位词分组题目描述解题思路步骤&#xff1a;时间复杂度&#xff1a;空间复杂度&#xff1a; 代码实现 3. 最长连续序列题目描述解题思路关键思路&#xff1a;…...

Jenkins 通过 Execute Shell 执行 shell 脚本 七

Jenkins 通过 Execute Shell 执行 shell 脚本 七 一、创建 .sh 文件 项目目录下新建 .sh 文件 jenkins-script\shell\ci_android_master.sh添加 Execute Shell 模块 在 Command 中添加 # 获取 .sh 路径 CI_ANDROID_MASTER_PATH"${WORKSPACE}/jenkins-script/shell/…...

无人机常见的定位方式

目录 1、卫星导航定位 2、基于地面基站定位 3、惯性导航定位 4、视觉定位 5、其他定位技术 目前无人机的定位方式主要有以下几种&#xff1a; 1、卫星导航定位 GPS 定位&#xff1a;全球定位系统是应用最广泛的卫星导航系统&#xff0c;无人机上的 GPS 接收器接收至少四…...

【Git版本控制器】:第一弹——Git初识,Git安装,创建本地仓库,初始化本地仓库,配置config用户名,邮箱信息

&#x1f381;个人主页&#xff1a;我们的五年 &#x1f50d;系列专栏&#xff1a;Linux网络编程 &#x1f337;追光的人&#xff0c;终会万丈光芒 &#x1f389;欢迎大家点赞&#x1f44d;评论&#x1f4dd;收藏⭐文章 ​ 相关笔记&#xff1a; https://blog.csdn.net/dj…...

使用 EDOT 监测由 OpenAI 提供支持的 Python、Node.js 和 Java 应用程序

作者&#xff1a;来自 Elastic Adrian Cole Elastic 很自豪地在我们的 Python、Node.js 和 Java EDOT SDK 中引入了 OpenAI 支持。它们为使用 OpenAI 兼容服务的应用程序添加日志、指标和跟踪&#xff0c;而无需任何代码更改。 介绍 去年&#xff0c;我们宣布了 OpenTelemetry…...

基于 STM32 的病房监控系统

标题:基于 STM32 的病房监控系统 内容:1.摘要 基于 STM32 的病房监控系统摘要&#xff1a;本系统采用 STM32 微控制器作为核心&#xff0c;通过传感器实时监测病房内的环境参数&#xff0c;如温度、湿度、光照等&#xff0c;并将数据上传至云端服务器。医护人员可以通过手机或…...

线上HBase client返回超时异常分析 HBase callTimeout=60000

问题现象 HBase client直接返回超时异常 HBase callTimeout=60000, callDuration=60301: row ‘12649160863966c2790195059018040900010003320’ on table ‘Z_UPA’ at region=Z_UPA,1213d1a56,1184027415643. ba7224f83dbb09591a74b7059f17., hostname=abcd,60020,891863950…...

03.开闭原则详细介绍

03.开闭原则详细介绍 目录介绍 01.问题思考的分析02.如何理解开闭原则03.开闭原则的背景04.开闭原则比较难学05.实现开闭原则方式06.画图形案例分析07.银行业务案例分析08.开闭原则优缺点09.开闭原则的总结 推荐一个好玩网站 一个最纯粹的技术分享网站&#xff0c;打造精品…...

前端职业规划

前端开发的职业规划可以根据个人兴趣、技术深度和职业目标来制定。以下是一个典型的前端开发者职业发展路径&#xff0c;涵盖了从初级到高级的不同阶段&#xff0c;以及未来的发展方向&#xff1a; 1. 初级阶段&#xff08;0-2 年&#xff09; 目标&#xff1a;掌握基础技能&a…...

杂记:STM32 调试信息打印实现方式

杂记&#xff1a;STM32 调试信息打印实现方式 一、引言二、使用 USART 串口打印原理&#xff08;二&#xff09;实现步骤硬件连接代码实现 使用 ST - LINK 调试器 ITM 打印&#xff08;一&#xff09;原理&#xff08;二&#xff09;实现步骤硬件连接代码实现 四、使用 Semihos…...

python+unity落地方案实现AI 换脸融合

先上效果再说技术结论&#xff0c;使用的是自行搭建的AI人脸融合库&#xff0c;可以离线不受限制无限次生成&#xff0c;有需要的可以后台私信python ai换脸融合。 TODO 未来的方向&#xff1a;3D人脸融合和AI数据训练 这个技术使用的是openvcinsighface&#xff0c;openvc…...

ComfyUI流程图生图原理详解

一、引言 ComfyUI 是一款功能强大的工具&#xff0c;在图像生成等领域有着广泛应用。本文补充一点ComfyUI 的安装与配置过程遇到的问题&#xff0c;并深入剖析图生图过程及相关参数&#xff0c;帮助读者快速入门并深入理解其原理。 二、ComfyUI 的安装与配置中遇到的问题 &a…...

【C++ 真题】P1824 进击的奶牛

P1824 进击的奶牛 题目描述 Farmer John 建造了一个有 N N N&#xff08; 2 ≤ N ≤ 1 0 5 2 \leq N \leq 10 ^ 5 2≤N≤105) 个隔间的牛棚&#xff0c;这些隔间分布在一条直线上&#xff0c;坐标是 x 1 , x 2 , ⋯ , x N x _ 1, x _ 2, \cdots, x _ N x1​,x2​,⋯,xN​&a…...

26、深度学习-自学之路-NLP自然语言处理-理解加程序,怎么把现实的词翻译给机器识别。

一、怎么能让机器能够理解我们的语言呢&#xff0c;我们可以利用神经网络干很多的事情&#xff0c;那么我们是不是也可以用神经元做自然语言处理呢&#xff0c;现在很多的实际应用已经说明了这个问题&#xff0c;可以这么做。 那我们考虑一下该怎么做&#xff0c;首先我们应该…...

24电子信息类研究生复试面试问题汇总 电子信息类专业知识问题最全!电子信息复试全流程攻略 电子信息考研复试真题汇总

你是不是在为电子信息考研复试焦虑&#xff1f;害怕被老师问到刁钻问题、担心专业面答不上来&#xff1f;别慌&#xff01;作为复试面试92分逆袭上岸的学姐&#xff0c;今天手把手教你拆解电子信息类复试通关密码&#xff01;看完这篇&#xff0c;让你面试现场直接开大&#xf…...

leetcode25. K 个一组翻转链表

代码如图所示&#xff1a;下面还有一个跑代码的流程图&#xff0c;结合两个图片理解起来就好&#xff0c;感觉已经解释的很清晰了&#xff01;&#xff01; 一定要记住return dummy.next;这表示伪节点的下一个节点才是反转完的整个链表的头结点 补一个最后的&#xff0c;有点纰…...

工厂方法模式详解(Java)

一、工厂方法模式基础 1.1 定义与角色 工厂方法模式(Factory Method Pattern)是一种创建型设计模式,它提供了一种创建对象的接口,但允许子类决定实例化哪一个类。这种模式的核心在于定义一个创建产品对象的工厂接口,将实际创建产品的过程延迟到子类中实现。这样做的主要…...

SpringBoot+Dubbo+zookeeper 急速入门案例

项目目录结构&#xff1a; 第一步&#xff1a;创建一个SpringBoot项目&#xff0c;这里选择Maven项目或者Spring Initializer都可以&#xff0c;这里创建了一个Maven项目&#xff08;SpringBoot-Dubbo&#xff09;&#xff0c;pom.xml文件如下&#xff1a; <?xml versio…...

pdf.js默认显示侧边栏和默认手形工具

文章目录 默认显示侧边栏(切换侧栏)默认手形工具(手型工具) 大部分的都是在viewer.mjs中的const defaultOptions 变量设置默认值,可以使用数字也可以使用他们对应的变量枚举值 默认显示侧边栏(切换侧栏) 在viewer.mjs中找到defaultOptions,大概在732行,或则搜索sidebarViewOn…...

数据库第三次作业

第一题&#xff1a; 学生表&#xff1a;Student (Sno, Sname, Ssex , Sage, Sdept) 学号&#xff0c;姓名&#xff0c;性别&#xff0c;年龄&#xff0c;所在系 Sno为主键 课程表&#xff1a;Course (Cno, Cname,) 课程号&#xff0c;课程名 Cno为主键 学生选课表&#xff1a;S…...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

【大模型RAG】Docker 一键部署 Milvus 完整攻略

本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装&#xff1b;只需暴露 19530&#xff08;gRPC&#xff09;与 9091&#xff08;HTTP/WebUI&#xff09;两个端口&#xff0c;即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

三体问题详解

从物理学角度&#xff0c;三体问题之所以不稳定&#xff0c;是因为三个天体在万有引力作用下相互作用&#xff0c;形成一个非线性耦合系统。我们可以从牛顿经典力学出发&#xff0c;列出具体的运动方程&#xff0c;并说明为何这个系统本质上是混沌的&#xff0c;无法得到一般解…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践

6月5日&#xff0c;2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席&#xff0c;并作《智能体在安全领域的应用实践》主题演讲&#xff0c;分享了在智能体在安全领域的突破性实践。他指出&#xff0c;百度通过将安全能力…...

Java入门学习详细版(一)

大家好&#xff0c;Java 学习是一个系统学习的过程&#xff0c;核心原则就是“理论 实践 坚持”&#xff0c;并且需循序渐进&#xff0c;不可过于着急&#xff0c;本篇文章推出的这份详细入门学习资料将带大家从零基础开始&#xff0c;逐步掌握 Java 的核心概念和编程技能。 …...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合

在汽车智能化的汹涌浪潮中&#xff0c;车辆不再仅仅是传统的交通工具&#xff0c;而是逐步演变为高度智能的移动终端。这一转变的核心支撑&#xff0c;来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒&#xff08;T-Box&#xff09;方案&#xff1a;NXP S32K146 与…...

恶补电源:1.电桥

一、元器件的选择 搜索并选择电桥&#xff0c;再multisim中选择FWB&#xff0c;就有各种型号的电桥: 电桥是用来干嘛的呢&#xff1f; 它是一个由四个二极管搭成的“桥梁”形状的电路&#xff0c;用来把交流电&#xff08;AC&#xff09;变成直流电&#xff08;DC&#xff09;。…...

边缘计算网关提升水产养殖尾水处理的远程运维效率

一、项目背景 随着水产养殖行业的快速发展&#xff0c;养殖尾水的处理成为了一个亟待解决的环保问题。传统的尾水处理方式不仅效率低下&#xff0c;而且难以实现精准监控和管理。为了提升尾水处理的效果和效率&#xff0c;同时降低人力成本&#xff0c;某大型水产养殖企业决定…...