Algorithm-HashMap
date
Oct 31, 2023
slug
algorithm-hashmap
status
Published
tags
algorithm
type
Post
https://twitter.com/tangdahe
summary
hashmap
242 有效的字母异位词
给定两个字符串
s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。注意：若
s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。349 两个数组的交集
给定两个数组
nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。202 快乐数
编写一个算法来判断一个数
n 是不是快乐数。「快乐数」 定义为：
- 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
- 如果这个过程 结果为 1，那么这个数就是快乐数。
如果
n 是 快乐数 就返回 true ；不是，则返回 false 。这道题目看上去貌似一道数学问题，其实并不是！
题目中说了会 无限循环，那么也就是说求和的过程中，sum会重复出现，这对解题很重要！
正如：关于哈希表，你该了解这些！ (opens new window)中所说，当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法了。
所以这道题目使用哈希法，来判断这个sum是否重复出现，如果重复了就是return false， 否则一直找到sum为1为止。
454 四数之和2
本题乍眼一看好像和三数之和 (opens new window)，四数之和 (opens new window)差不多，其实差很多。
本题是使用哈希法的经典题目，而三数之和 (opens new window)，四数之和 (opens new window)并不合适使用哈希法，因为三数之和和四数之和这两道题目使用哈希法在不超时的情况下做到对结果去重是很困难的，很有多细节需要处理。
而这道题目是四个独立的数组，只要找到 A[i] + B[j] + C[k] + D[l] = 0就可以，不用考虑有重复的四个元素相加等于0的情况，所以相对于四数之和三数之和，还是简单了不少！
如果本题想难度升级：就是给出一个数组（而不是四个数组），在这里找出四个元素相加等于0，答案中不可以包含重复的四元组，大家可以思考一下，后续的文章我也会讲到的。
本题解题步骤：
- 首先定义 一个 map，key 放 a 和 b 两数之和，value 放 a 和 b 两数之和出现的次数。
- 遍历大 A 和大 B 数组，统计两个数组元素之和，和出现的次数，放到 map 中。
- 定义 int 变量 count，用来统计 a+b+c+d = 0 出现的次数。
- 在遍历大 C 和大 D 数组，找到如果 0-(c+d) 在 map 中出现过的话，就用 count 把 map 中 key 对应的 value 也就是出现次数统计出来。
- 最后返回统计值 count 就可以了
15 三数之和
其实这道题目使用哈希法并不十分合适，因为在去重的操作中有很多细节需要注意，在面试中很难直接写出没有 bug 的代码。
而且使用哈希法 在使用两层 for 循环的时候，能做的剪枝操作很有限，虽然时间复杂度是O(n^2)，也是可以在 leetcode 上通过，但是程序的执行时间依然比较长 。
接下来我来介绍另一个解法：双指针法，这道题目使用双指针法 要比哈希法高效一些，那么来讲解一下具体实现的思路。
动画效果如下：
拿这个 nums 数组来举例，首先将数组排序，然后有一层 for 循环，i 从下标 0 的地方开始，同时定一个下标 left 定义在 i+1 的位置上，定义下标 right 在数组结尾的位置上。
依然还是在数组中找到 abc 使得 a + b +c =0，我们这里相当于 a = nums[i]，b = nums[left]，c = nums[right]。
接下来如何移动 left 和 right 呢， 如果 nums[i] + nums[left] + nums[right] > 0 就说明 此时三数之和大了，因为数组是排序后了，所以 right 下标就应该向左移动，这样才能让三数之和小一些。
如果 nums[i] + nums[left] + nums[right] < 0 说明 此时 三数之和小了，left 就向右移动，才能让三数之和大一些，直到 left 与 right 相遇为止。
时间复杂度：O(n^2)。
18 四数之和