标签:下标 哈希 有关 元素 算法 数组 表中 例题
例题一
解法(哈希表):
算法思路:
•
如果我们可以事先将「数组内的元素」和「下标」绑定在⼀起存⼊「哈希表」中,然后直接在哈希表中查找每⼀个元素的 target - nums[i]
,就能快速的找到「⽬标和的下标」。
•
这⾥有⼀个⼩技巧,我们可以不⽤将元素全部放⼊到哈希表之后,再来⼆次遍历(因为要处理元素相同的情况)。⽽是在将元素放⼊到哈希表中的「同时」,直接来检查表中是否已经存在当前元素所对应的⽬标元素(即 target - nums[i]
)。如果它存在,那我们已经找到了对应解,并⽴即将其返回。⽆需将元素全部放⼊哈希表中,提⾼效率。
•
因为哈希表中查找元素的时间复杂度是 O(1)
,遍历⼀遍数组的时间复杂度为
O(N)
,因此可以
将时间复杂度降到
O(N)
。这是⼀个典型的「⽤空间交换时间」的⽅式。
例题二
解法(哈希表):
算法思路:
1.
当两个字符串的⻓度不相等的时候,是不可能构成互相重排的,直接返回 false
;
2.
如果两个字符串能够构成互相重排,那么每个字符串中「各个字符」出现的「次数」⼀定是相同
的。因此,我们可以分别统计出这两个字符串中各个字符出现的次数,然后逐个⽐较是否相等即
可。这样的话,我们就可以选择「哈希表」来统计字符串中字符出现的次数。
例题三
解法(哈希表):
算法思路:
分析⼀下题⽬,出现「⾄少两次」的意思就是数组中存在着重复的元素,因此我们可以⽆需统计元素出现的数⽬。仅需在遍历数组的过程中,检查当前元素「是否在之前已经出现过」即可。
因此我们可以利⽤哈希表,仅需存储数「组内的元素」。在遍历数组的时候,⼀边检查哈希表中是否已经出现过当前元素,⼀边将元素加⼊到哈希表中。
例题四
解法(哈希表):
算法思路:
解决该问题需要我们快速定位到两个信息:
•
两个相同的元素;
•
这两个相同元素的下标。
因此,我们可以使⽤「哈希表」,令数组内的元素做
key
值,该元素所对应的下标做
val
值,将
「数组元素」和「下标」绑定在⼀起,存⼊到「哈希表」中。
思考题: 如果数组内存在⼤量的「重复元素」,⽽我们判断下标所对应的元素是否符合条件的时候,需要将不同下标的元素作⽐较,怎么处理这个情况呢?
答:这⾥运⽤了⼀个「⼩贪⼼」。 我们按照下标「从⼩到⼤」的顺序遍历数组,当遇到两个元素相同,并且⽐较它们的下标时,这两个下标⼀定是距离最近的,因为:
•
如果当前判断符合条件直接返回 true
,⽆需继续往后查找。
•
如果不符合条件,那么前⼀个下标⼀定不可能与后续相同元素的下标匹配(因为下标在逐渐变⼤),那么我们可以⼤胆舍去前⼀个存储的下标,转⽽将其换成新的下标,继续匹配。
例题五
解法(哈希表 + 排序):
算法思路:
互为字⺟异位词的单词有⼀个特点:将它们「排序」之后,两个单词应该是「完全相同」的。
所以,我们可以利⽤这个特性,将单词按照字典序排序,如果排序后的单词相同的话,就划分到同⼀组中。
这时我们就要处理两个问题:
•
排序后的单词与原单词需要能互相映射;
•
将排序后相同的单词,「划分到同⼀组」;
利⽤语⾔提供的「容器」的强⼤的功能就能实现这两点:
•
将排序后的字符串( string )当做哈希表的
key
值;
•
将字⺟异位词数组( string[] )当成
val
值。 定义⼀个「哈希表」即可解决问题。
标签:下标,
哈希,
有关,
元素,
算法,
数组,
表中,
例题
From: https://blog.csdn.net/2301_79881188/article/details/137400623