【LeetCode】哈希表题解汇总

写在前面

这里是小飞侠Pan🥳，立志成为一名优秀的前端程序媛！！！

本篇文章同时收录于我的github前端笔记仓库中，持续更新中，欢迎star~

👉https://github.com/mengqiuleo/myNote

1. 两数之和

1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
1
2
3

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]
1
2

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]
1
2

题解思路

• 用哈希表存储每个元素，key为值，value为下标
• 从头遍历每个元素，对于nums[i]，根据给定的target，那么另一个数应该为target-nums[i]
• 如果这个数target-nums[i]在哈希表中出现了，说明已找到答案

var twoSum = function(nums, target) {
    let hash = {};
    for(let i = 0; i < nums.length; i++){
        if(hash[target - nums[i]] !== undefined){
            return [i, hash[target - nums[i]]];
        }
        hash[nums[i]] = i;
    }
    return [];
};
1
2
3
4
5
6
7
8
9
10

36. 有效的数独

36. 有效的数独

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

注意：

一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
空白格用 ‘.’ 表示。

示例 2：

输入：board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：false
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
1
2
3
4
5
6
7
8
9
10
11
12

题解思路

• 首先需要三个哈希表来记录行，列，3*3小方块里面的数值情况

• 遍历每一个值，分别判断上面三种情况：是否出现重复

• 注意点：求得该数值在哪个小方块：parseInt((i/3))*3 + parseInt(j/3)

  

var isValidSudoku = function(board) {
    let rows = {};//行
    let columns = {};//列
    let boxes = {};//3*3小方块
    for(let i = 0; i < 9; i++){
        for(let j = 0; j < 9; j++){
            let num = board[i][j];
            if(num != '.'){//遇到有效的数字
                let boxIndex = parseInt((i/3))*3 + parseInt(j/3);//子数独序号：即位于第几个小方块
                if(rows[i+'-'+num] || columns[j+'-'+num] || boxes[boxIndex+'-'+num]){
                    return false;
                }
                //记录当前的值
                rows[i+'-'+num] = true;
                columns[j+'-'+num] = true;
                boxes[boxIndex+'-'+num] = true;
            }
        }
    }
    return true;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

41. 缺失的第一个正数

41. 缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1：

输入：nums = [1,2,0]
输出：3
1
2

示例 2：

输入：nums = [3,4,-1,1]
输出：2
1
2

示例 3：

输入：nums = [7,8,9,11,12]
输出：1
1
2

题解思路

var firstMissingPositive = function(nums) {
    for(let i = 0; i < nums.length; i++){
        while(nums[i] > 0 && nums[i] <= nums.length && nums[nums[i]-1] != nums[i]){
            [ nums[nums[i]-1], nums[i] ] = [ nums[i], nums[nums[i]-1] ];
        }
    }
    for(let i = 0; i < nums.length; i++){
        if(nums[i] != i + 1){
            return i + 1;
        }
    }
    return nums.length + 1;
};
1
2
3
4
5
6
7
8
9
10
11
12
13

题解思路

• 题目要求返回缺失的第一个正整数，那么我们可以采用“一个萝卜一个坑”的思想
• 将数组中的所有数字归位，当下标为[0,N]时，数字应该为[1,N+1]
• 那么数值为i的数应该放在下标为i-1的位置
• 比如数字：nums[i]，它的下标应该为nums[i]-1，
• 所以，反过来说，下标为nums[i]-1的地方对应的数字应该为nums[nums[i]-1]
• 通过上面的推导，我们可以得出一个结论：nums[nums[i]-1] === nums[i]
• 于是，我们可以遍历一遍，将所有的数组交换到正确的位置，然后再进行一次遍历，找到nums[i] != i + 1的数

这个题要重点理解：nums[nums[i]-1] === nums[i] 的意思

var firstMissingPositive = function(nums) {
    for(let i = 0; i < nums.length; i++){
        while(nums[i] > 0 && nums[i] <= nums.length && nums[nums[i]-1] != nums[i]){
            [ nums[nums[i]-1], nums[i] ] = [ nums[i], nums[nums[i]-1] ];
        }
    }
    for(let i = 0; i < nums.length; i++){
        if(nums[i] != i + 1){
            return i + 1;
        }
    }
    return nums.length + 1;
};
1
2
3
4
5
6
7
8
9
10
11
12
13

49. 字母异位词分组

49. 字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
1
2

示例 2:

输入: strs = [""]
输出: [[""]]
1
2

示例 3:

输入: strs = ["a"]
输出: [["a"]]
1
2

题解思路

• 用res数组存放最终的答案
• map：key存放以排序号好的字母组合，value是一个数组，存放所有相同的字母组合

var groupAnagrams = function(strs) {
    let res = [];
    let map = new Map();
    for(let i = 0; i < strs.length; i++){
        let k = strs[i].split('').sort().join('');
        if(map.has(k)){
            map.get(k).push(strs[i]);
        } else {
            map.set(k,[strs[i]]);
        }
    }
    map.forEach((value, key) => {
        res.push(value);
    })
    return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

202. 快乐数

202. 快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

示例 1：

输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
1
2
3
4
5
6
7

示例 2：

输入：n = 2
输出：false
1
2

题解思路

先举几个例子。我们从 7 开始。则下一个数字是 49（因为 7*7=49），然后下一个数字是 97（因为 4²⁺⁹2=97）。我们可以不断重复该的过程，直到我们得到 1。因为我们得到了 1，我们知道 7 是一个快乐数，函数应该返回 true。

再举一个例子，让我们从 116 开始。通过反复通过平方和计算下一个数字，我们最终得到 58，再继续计算之后，我们又回到 58。由于我们回到了一个已经计算过的数字，可以知道有一个循环，因此不可能达到 1。所以对于 116，函数应该返回 false。

var squareSum = (n) => { // 求出平方的功能函数
    let sum = 0;
    while(n > 0){
        let digit = n % 10;
        sum += digit * digit;
        n = Math.floor(n /10);
    }
    return sum;
}

var isHappy = function(n) {
    let slow = n, fast = squareSum(n);
    //有可能第一步就判断出是快乐数
    while(fast !== 1){
        slow = squareSum(slow);
        fast = squareSum(squareSum(fast));
        if(slow === fast){
            return false;
        }
    }
    return fast === 1;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

205. 同构字符串

205. 同构字符串

给定两个字符串 s 和 t ，判断它们是否是同构的。

如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。

每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

示例 1:

输入：s = "egg", t = "add"
输出：true
1
2

示例 2：

输入：s = "foo", t = "bar"
输出：false
1
2

示例 3：

输入：s = "paper", t = "title"
输出：true
1
2

题解思路

举个具体的例子。

egg 和 add 同构，就意味着下边的映射成立
e -> a
g -> d
也就是将 egg 的 e 换成 a, g 换成 d, 就变成了 add

同时倒过来也成立
a -> e
d -> g
也就是将 add 的 a 换成 e, d 换成 g, 就变成了 egg

foo 和 bar 不同构，原因就是映射不唯一
o -> a
o -> r
其中 o 映射到了两个字母
1
2
3
4
5
6
7
8
9
10
11
12
13
14

我们可以利用一个 map 来处理映射。对于 s 到 t 的映射，我们同时遍历 s 和 t ，假设当前遇到的字母分别是 c1 和 c2 。

如果 map[c1] 不存在，那么就将 c1 映射到 c2 ，即 map[c1] = c2。

如果 map[c1] 存在，那么就判断 map[c1] 是否等于 c2，也就是验证之前的映射和当前的字母是否相同。

注意：

对于这道题，我们只需要验证 s -> t 和 t -> s 两个方向即可。如果验证一个方向，是不可以的。

举个例子，s = ab, t = cc，如果单看 s -> t ，那么 a -> c, b -> c 是没有问题的。

必须再验证 t -> s，此时，c -> a, c -> b，一个字母对应了多个字母，所以不是同构的。

var isIsomorphic = function(s, t) {
    let len = s.length;
    const sMap = new Map(), tMap = new Map();
    for(let i = 0; i < len; i++){
        const sValue = sMap.get(s[i]);
        const tValue = tMap.get(t[i]);
        if((sValue && sValue !== t[i]) || (tValue && tValue !== s[i])){
            return false;
        }
        sMap.set(s[i], t[i]);//建立双层关系
        tMap.set(t[i], s[i]);
    }
    return true;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

217. 存在重复元素

217. 存在重复元素

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

示例 1：

输入：nums = [1,2,3,1]
输出：true
1
2

示例 2：

输入：nums = [1,2,3,4]
输出：false
1
2

示例 3：

输入：nums = [1,1,1,3,3,4,3,2,4,2]
输出：true
1
2

题解思路

var containsDuplicate = function(nums) {
    let map = new Map();
    let len = nums.length;
    for(let i = 0; i < len; i++){
        if(map.has(nums[i])){
            return true;
        }
        map.set(nums[i], 1);
    }
    return false;
};
1
2
3
4
5
6
7
8
9
10
11

219. 存在重复元素 II

219. 存在重复元素 II

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [1,2,3,1], k = 3
输出：true
1
2

示例 2：

输入：nums = [1,0,1,1], k = 1
输出：true
1
2

示例 3：

输入：nums = [1,2,3,1,2,3], k = 2
输出：false
1
2

题解思路

• 维护一个哈希表，里面始终最多包含 k 个元素，当出现重复值时则说明在 k 距离内存在重复元素
• 每次遍历一个元素则将其加入哈希表中，如果哈希表的大小大于 k，则移除最前面的数字

画图模拟：画解算法：219. 存在重复元素 II

var containsNearbyDuplicate = function(nums, k) {
    const map = new Map();
    for(let i = 0; i < nums.length; i++){
        if(map.has(nums[i])){
            return true;
        }
        map.set(nums[i],1);
        if(map.size > k){
            map.delete(nums[i - k]);
        }
    }
    return false;
};
1
2
3
4
5
6
7
8
9
10
11
12
13

242. 有效的字母异位词

242. 有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

示例 1:

输入: s = "anagram", t = "nagaram"
输出: true
1
2

示例 2:

输入: s = "rat", t = "car"
输出: false
1
2

题解思路

• 首先使用一个map存放每个字符串的字母信息
• 然后循环遍历，对两个map进行比较

var getMap = function(str){ //得到每个字符串的map
    //if(typeof str !== 'string') return false;
    let map = new Map();
    for(let i of str){
        if(map.has(i)){
            map.set(i, map.get(i) + 1);
        }else{
            map.set(i, 1);
        }
    }
    return map;
}

var compareTwoMap = function(map1, map2){ //比较两个map
    if(map1.size !== map2.size) return false;
    if(map1.size === map2.size && map1.size === 0) return true;
    for(let i  of map1.keys()){
        if(!map2.has(i)) return false;
        if(map1.get(i) !== map2.get(i)) return false;
    }
    return true;
}

var isAnagram = function(s, t) {
    return compareTwoMap(getMap(s), getMap(t));
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

290. 单词规律

290. 单词规律

给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。

这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。

示例1:

输入: pattern = "abba", s = "dog cat cat dog"
输出: true
1
2

示例 2:

输入:pattern = "abba", s = "dog cat cat fish"
输出: false
1
2

示例 3:

输入: pattern = "aaaa", s = "dog cat cat dog"
输出: false
1
2

题解思路

这个题和 205. 同构字符串相似

我们还是使用两个map来存储对应的映射关系

var wordPattern = function(pattern, s) {
    const patternMap = new Map(), sMap = new Map();
    const words = s.split(' ');
    if (pattern.length !== words.length) {
        return false;
    }
    for(const [i, word] of words.entries()){
        const ch = pattern[i];
        if((patternMap.has(word) && patternMap.get(word) !== ch) || (sMap.has(ch) && sMap.get(ch) !== word)){
            return false;
        }
        patternMap.set(word, ch);
        sMap.set(ch, word);
    }
    return true;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

349. 两个数组的交集

349. 两个数组的交集

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
1
2

示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的
1
2
3

题解思路

var intersection = function(nums1, nums2) {
    let set = new Set(nums1);
    return [...new Set(nums2)].filter(val => set.has(val));
};
1
2
3
4

350. 两个数组的交集 II

350. 两个数组的交集 II

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]
1
2

示例 2:

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]
1
2

题解思路

这个题和上面的那个题的不同点是：我们可以返回相同的值，不需要去重。

那就可以采用“一一对应”的思想。

遍历一个数组，如果某个元素在另一个数组中出现，那就要把它返回，并且要把另一个数组的该值去除。

var intersect = function(nums1, nums2) {
    const res = [];
    nums2.forEach((item) => {
        const index = nums1.indexOf(item);
        if(index !== -1){
            res.push(item);
            nums1[index] = null;
        } 
    })
    return res;
};
1
2
3
4
5
6
7
8
9
10
11

383.赎金信

383. 赎金信

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

示例 1：

输入：ransomNote = "a", magazine = "b"
输出：false
1
2

示例 2：

输入：ransomNote = "aa", magazine = "ab"
输出：false
1
2

示例 3：

输入：ransomNote = "aa", magazine = "aab"
输出：true
1
2

题解思路

用一个映射记录magazine字符串中的字母及出现次数

然后遍历ransomNote字符串，此时必须要保证ransomNote字符串中的某个字母出现在哈希表中，否则返回false。

var canConstruct = function(ransomNote, magazine) {
    const store = {};
    for(let i = 0; i < magazine.length; i++){
        if(!store[magazine[i]]){
            store[magazine[i]] = 1;
        } else {
            store[magazine[i]]++;
        }
    }
    for(let i = 0; i < ransomNote.length; i++){
        if(store[ransomNote[i]]){
            store[ransomNote[i]]--;
        } else {
            return false;
        }
    }
    return true;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

454. 四数相加 II

454. 四数相加 II

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

示例 1：

输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：

1.(0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0

2.(1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0
1
2
3
4
5
6
7
8

示例 2：

输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出：1
1
2

题解思路

思路：在A和B中取出两个数的组合，将这两个数的和作为键，出现次数作为值加入哈希表中，循环C、D，判断C和D中是否存在两个数的和 加 AB中的俩元素的和正好是0，统计组合数

四数相加，转化为两数相加，降低时间复杂度。

var fourSumCount = function(nums1, nums2, nums3, nums4) {
    const twoSumMap = new Map();
    let count = 0;

    for(const n1 of nums1){
        for(const n2 of nums2){
            const sum = n1 + n2;
            twoSumMap.set(sum, (twoSumMap.get(sum) || 0) + 1);
        }
    }

    for(const n3 of nums3){
        for(const n4 of nums4){
            const sum = n3 + n4;
            count += (twoSumMap.get(0 - sum) || 0)
        }
    }
    return count;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19