代码随想录训练营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;
};