【算法-哈希表】常见算法题的哈希表套路拆解

请添加图片描述

算法相关知识点可以通过点击以下链接进行学习一起加油!
双指针滑动窗口二分查找前缀和位运算
模拟链表

在刷题的过程中,我们会频繁遇到一些“高频套路”——而哈希表正是其中最常用也最高效的工具之一。它能帮助我们在 O(1) 的时间复杂度内完成查找、插入与删除操作。
本文将围绕常见的算法题场景,系统性地拆解哈希表的应用思路,帮助你快速识别题型、构建解题模板,并提升解题效率。

请添加图片描述

Alt

🌈个人主页:是店小二呀
🌈C/C++专栏:C语言\ C++
🌈初/高阶数据结构专栏: 初阶数据结构\ 高阶数据结构
🌈Linux专栏: Linux
🌈算法专栏:算法
🌈Mysql专栏:Mysql

🌈你可知:无人扶我青云志 我自踏雪至山巅 请添加图片描述

文章目录

  • 一、哈希表概念
  • 二、哈希表作用
  • 三、如何使用哈希表
    • 1. 两数之和
    • 面试题 01.02. 判定是否互为字符重排
    • 217. 存在重复元素
    • 219. 存在重复元素 II
    • LCR 033. 字母异位词分组

一、哈希表概念

哈希表就像是一个很智能的储物柜,每个数据都有一个特定的“标签”(哈希值),通过这个标签可以直接找到数据存放的位置,而不用遍历所有的内容

二、哈希表作用

哈希表的作用可以概括为:

  1. 快速查找:哈希表通过哈希函数把元素映射到数组的索引位置,使得查找操作非常快速,接近常数时间复杂度(O(1))。
  2. 元素标记:配合布尔数组使用,可以方便地标记某个元素是否存在,适用于去重或记录状态等场景。
  3. 统计频次:利用哈希表记录元素出现的次数,能够高效地进行频率统计,无需遍历整个数据集。
  4. 字符串连续下标:对于字符串等数据,哈希表可以通过哈希值将其映射到连续的下标上,便于快速索引和操作。

三、如何使用哈希表

  1. 容器(哈希表)

  2. 用数组模拟简易哈希表:字符串中的"字符" 和 “数据范围很小的时候”

1. 两数之和

题目】:1. 两数之和

在这里插入图片描述

算法思路

解法一:暴力解法

  1. 先固定其中一个数

  2. 依次与该数之前的数相加

解法二:使用哈希表来优化

在这里插入图片描述

这道题与“560. 和为 K 的子数组”类似,利用了哈希表的特性。通过哈希表的 count 接口,可以迅速判断前面是否已经出现过相关元素,实现了快速查找。具体来说,问题通过 targetnums[i] 之间的等价关系,将原本的问题转化为寻找前面已出现元素的哈希查找问题。

哈希表存储数组元素及其对应的下标,便于快速访问和操作数组元素。

代码实现

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> hash;for(int i = 0; i < nums.size(); i++){int ret = target - nums[i];if(hash.count(ret)) return {i, hash[ret]};hash[nums[i]] = i;}return {-1, -1};}
};

面试题 01.02. 判定是否互为字符重排

题目】:面试题 01.02. 判定是否互为字符重排

在这里插入图片描述

算法思路

在这里插入图片描述

哈希表不关心元素的顺序,只要是数据就存进去,然后通过哈希值来判断元素是否相等

优化方案

只使用一个哈希表进行统计,然后在遍历另一个哈希表时不断减少对应元素的计数。如果哈希表中的元素次数为0,说明两个字符串相同。由于只涉及小写字母,我们可以用一个大小为26的数组来模拟哈希表,从而减少空间开销。

代码实现

class Solution {
public:bool CheckPermutation(string s1, string s2){int n = s1.size();if(n != s2.size()) return false;int hash[26] = {0};for(auto ch: s1)hash[ch - 'a']++;for(auto x : s2){hash[x - 'a']--;if(hash[x - 'a'] < 0) return false;}return true;}
};

217. 存在重复元素

题目】:217. 存在重复元素

在这里插入图片描述

算法思路

判断是否存在重复元素,哈希表中count接口可以查看先前是否存储相关元素,同当前nums[i]判断,意思就是之前的数等于nums[i],当前遍历到nums[i],说明存在重复元素

代码实现

class Solution {
public:bool containsDuplicate(vector<int>& nums) {//只需要判断是否重现即可,不需要得知次数unordered_setint, int> hash;for(auto x : nums){if(hash.count(x)) return true;else hash.insert(x);}return false;}

219. 存在重复元素 II

题目】:219. 存在重复元素 II
在这里插入图片描述

算法思路

我们可以通过哈希表来实现快速查找。遍历数组时,对于每个元素 nums[i],我们在哈希表中查看是否已经出现过该元素。如果出现过,判断当前下标 i 与之前相同元素的下标差是否小于等于 k,若满足条件,则返回 true,表示存在满足条件的重复元素。如果遍历结束都没有找到满足条件的元素,则返回 false

代码实现

class Solution {
public:bool containsNearbyDuplicate(vector<int>& nums, int k) {unordered_map<int, int> hash;for(int i = 0; i < nums.size(); i++){if(hash.count(nums[i])){if(i - hash[nums[i]] <= k) return true;}hash[nums[i]] = i;}return false;}
};

LCR 033. 字母异位词分组

题目】:LCR 033. 字母异位词分组

在这里插入图片描述

算法思路

在这里插入图片描述

遍历字符串数组,将每个字符串排序后,利用哈希表的 first 存储已排序的字符串作为键,对应的值存储原始字符串。这里充分利用了哈希表作为存储容器的特性。最终,返回字符串数组时,可以通过 auto& [x, y] : hash 来遍历哈希表,这样就能方便地取出每一项的“键”和“值”,并直接使用它们。

代码实现

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map<string, vector<string>> hash;for(auto& s : strs){string tmp = s;sort(tmp.begin(), tmp.end());hash[tmp].push_back(s);}vector<vector<string>> ret;for(auto&[x,y] : hash){ret.push_back(y);}return ret;}
};

在这里插入图片描述
快和小二一起踏上精彩的算法之旅!关注我,我们将一起破解算法奥秘,探索更多实用且有趣的知识,开启属于你的编程冒险!

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

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

相关文章

异地多活单元化架构下的微服务体系

治理服务间的跨IDC调用&#xff0c;而数据库层面还是要跨IDC 服务注册中心拆开、 金融要求&#xff0c;距离太远&#xff0c;异地备库&#xff0c;如果延迟没读到数据就可能有资损&#xff0c;IDC3平时不能用&#xff0c;IDC1挂了还是有数据同步问题&#xff0c;IDC3日常维护…

python打卡day20

特征降维------特征组合&#xff08;以SVD为例&#xff09; 知识点回顾&#xff1a; 奇异值的应用&#xff1a; 特征降维&#xff1a;对高维数据减小计算量、可视化数据重构&#xff1a;比如重构信号、重构图像&#xff08;可以实现有损压缩&#xff0c;k 越小压缩率越高&#…

【C/C++】范围for循环

&#x1f4d8; C 范围 for 循环详解&#xff08;Range-based for loop&#xff09; 一、什么是范围 for 循环&#xff1f; 范围 for 循环&#xff08;Range-based for loop&#xff09; 是 C11 引入的一种简化容器/数组遍历的方式。它通过自动调用容器的 begin() 和 end() 方法…

MySQL 与 Elasticsearch 数据一致性方案

MySQL 与 Elasticsearch 数据一致性方案 前言一、同步双写&#xff08;Synchronous Dual Write&#xff09;&#x1f504;二、异步双写&#xff08;Asynchronous Dual Write&#xff09;&#x1f4e4;三、定时同步&#xff08;Scheduled Synchronization&#xff09;&#x1f5…

【相机标定】OpenCV 相机标定中的重投影误差与角点三维坐标计算详解

摘要&#xff1a; 本文将从以下几个方面展开&#xff0c;结合典型代码深入解析 OpenCV 中的相机标定过程&#xff0c;重点阐述重投影误差的计算方法与实际意义&#xff0c;并通过一个 calcBoardCornerPositions() 函数详细讲解棋盘格角点三维坐标的构建逻辑。 在计算机视觉领域…

【MySQL】联合查询

个人主页&#xff1a;♡喜欢做梦 欢迎 &#x1f44d;点赞 ➕关注 ❤️收藏 &#x1f4ac;评论 目录 一、什么是联合查询 1.概念 2.语法要求 3.示例 4.为什么要使用联合查询 内连接 1.概念 2.语法 3.步骤&#xff1a; 外连接 1.概念 2.分类&#xff1a; 左外连…

如何从极狐GitLab 容器镜像库中删除容器镜像?

极狐GitLab 是 GitLab 在中国的发行版&#xff0c;关于中文参考文档和资料有&#xff1a; 极狐GitLab 中文文档极狐GitLab 中文论坛极狐GitLab 官网 从容器镜像库中删除容器镜像 (BASIC ALL) 您可以从您的容器镜像库中删除容器镜像。 要基于特定标准自动删除容器镜像&#x…

【Git】【commit】查看未推送的提交查看指定commit的修改内容合并不连续的commit

文章目录 1. 查看未推送的提交方法一 &#xff1a;git status方法二&#xff1a;git log方法三&#xff1a;git cherry方法四&#xff1a;git rev-list 2. 查看指定commit的修改方法一&#xff1a;git show方法二&#xff1a;git log方法三&#xff1a;git diff 3. 合并不连续的…

神经网络—感知器、多层感知器

文章目录 前言一、生物神经元与感知器的类比二、感知器1、简单感知器2、多层感知器&#xff08;1&#xff09;多层感知机结构 3、神经网络结构 总结1、感知器的局限性如何突破感知器的局限性&#xff1f; 2、感知器的应用 前言 感知器&#xff08;Perceptron&#xff09;是神经…

C++:扫雷游戏

一.扫雷游戏项目设计 1.文件结构设计 首先我们要先定义三个文件 ①test.c //文件中写游戏的测试逻辑 ②game.c //文件中写游戏中函数的实现等 ③game.h //文件中写游戏需要的数据类型和函数声明等 2.扫雷游戏的主体结构 使⽤控制台实现经典的扫雷游戏 •游戏可以通过菜单…

k8s的pod挂载共享内存

k8s的pod挂载共享内存&#xff0c;限制不生效问题&#xff1a; 注&#xff1a;/dev/shm 是 Linux 系统中用于共享内存的特殊路径。通过将 emptyDir 的 medium 设置为 Memory&#xff0c;可以确保 /dev/shm 正确地挂载到一个基于内存的文件系统&#xff0c;从而实现高效的共享内…

【Linux学习笔记】基础IO之理解文件

【Linux学习笔记】基础IO之理解文件 &#x1f525;个人主页&#xff1a;大白的编程日记 &#x1f525;专栏&#xff1a;Linux学习笔记 前言 哈喽&#xff0c;各位小伙伴大家好!上期我们讲了进程替换 今天我们讲的是基础IO之理解文件。话不多说&#xff0c;我们进入正题&#…