代码随想录训练营Day6|242. 有效的字母异位词，349.
今天学习哈希表
一般哈希表都是用来快速判断一个元素是否出现集合里
242. 有效的字母异位词
题目描述：
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
示例 1:
输入: s = "anagram", t = "nagaram"
输出: true
示例 2:
输入: s = "rat", t = "car"
输出: false
解题思路
- 遍历字符串s，利用map记录各个字符出现的次数
- 遍历字符串t，如果 t 中的字符在map中出现，则对应数值减1，如果 t 中的字符没有出现，或者直到数值小于0 ，则不为字母异位词
- 否则互为字母异位词
var isAnagram = function(s, t) {
if (s.length !== t.length) {
return false
}
let record = new Map()
for (let item of s) {
record.set(item, (record.get(item) || 0) + 1)
}
for (let item of t) {
if (!record.get(item) || record.get(item) < 0) {
return false
}
record.set(item, (record.get(item) || 0) - 1)
}
return true;
};
349. 两个数组的交集
题目描述：
给定两个数组 nums1 和 nums2 ，返回它们的交集 。输出结果中的每个元素一定是唯一的。我们可以 不考虑输出结果的顺序 。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的
解题思路
实现一
- 利用map记录nums1中的元素
- 再遍历nums2中的元素，如果存在map中，并且结果数组res中不存在，那么添加到结果数组中
var intersection = function(nums1, nums2) {
let res = [];
let record = new Map();
for (let i of nums1) {
record.set(i, 1)
}
for (let i of nums2) {
if (record.get(i) && !res.includes(i)) {
res.push(i)
}
}
return res;
};
实现二
- 直接利用set存储结果值，不用考虑会出现重复的元素了
var intersection = function(nums1, nums2) {
let res = new Set();
let record = new Map();
for (let i of nums1) {
record.set(i, 1)
}
for (let i of nums2) {
if (record.get(i)) {
res.add(i)
}
}
return Array.from(res);
};
202. 快乐数
题目描述：
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为：
对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false。
示例 1：
输入：n = 19
输出：true
解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1
示例 2：
输入：n = 2
输出：false
提示：
1 <= n <= 2^31 - 1
解题思路
- 重复上述计算过程，如果出现 1 为快乐数，如果出现无限循环，则说明某个计算和会重复出现，如果重复出现且不为 1 ，那么则不为快乐数。
- 对 n 的各个位依次求和
- 记录求和出现次数，判断是否再次出现
var isHappy = function(n) {
let map = new Map()
// 求各个位的平方和
function getSum (n) {
let sum = 0;
while(n) {
sum += (n % 10) * (n % 10);
n = Math.floor(n / 10)
}
return sum;
}
while(true) {
if (map.has(n)) {
return false
}
if (n === 1) {
return true
}
map.set(n, 1)
n = getSum(n)
}
};
1. 两数之和
题目描述：
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
解题思路
- 使用 map 存储元素，值为对应索引
- 利用差值，与 map 中的元素进行比较，如果相等，则找到已存在的元素，及当前比较元素的索引
var twoSum = function(nums, target) {
let map = new Map();
let res = [];
for (let i = 0; i < nums.length; i++) {
if (!map.has(target - nums[i])) {
map.set(nums[i], i)
} else {
res = [map.get(target - nums[i]), i]
}
}
return res;
};
