【LeetCode与《代码随想录》】哈希表篇：做题笔记与总结-JavaScript版

代码随想录

代码随想录
代码随想录CSDN官方

主要题目

242. 有效的字母异位词

242. 有效的字母异位词

var isAnagram = function (s, t) {
    if (s.length !== t.length) return false;

    let ss = new Array(26).fill(0);
    // base 字母的Unicode编码
    let base = 'a'.charCodeAt();

    for (let i of s) {
        ss[i.charCodeAt() - base]++;
        // console.log(i.charCodeAt()-base);
    }
    for (let i of t) {
        ss[i.charCodeAt() - base]--;
        // console.log(i.charCodeAt()-base);
    }

    let flag = 0;
    ss.forEach(function (item) {
        if (item) {
            flag = 1;
        }
    })
    if (flag) return false;
    return true;
};
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

349. 两个数组的交集

349. 两个数组的交集

//  在大的里面找小的,set1大
const setIntersection = function (set1, set2) {
    if (set1.length < set2.length) {
        return setIntersection(set2, set1);
    }

    let ans = new Set();
    for (let i of set2) {
        if (set1.has(i)) {
            ans.add(i);
        }
    }

    return Array.from(ans)

}

var intersection = function (nums1, nums2) {
    let set1 = new Set(nums1);
    let set2 = new Set(nums2);
    return setIntersection(set1, set2);
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

202. 快乐数

202. 快乐数

var isHappy = function (n) {
    const happy = function (n) {
        let ans = 0;
        while (n) {
            ans += (n % 10) ** 2;
            // 要向下取整
            n = Math.floor(n / 10);
        }
        return ans;
    }

    let set = new Set();
    while (n != 1) {
        let temp = happy(n);
        if (set.has(temp)) return false;
        else {
            set.add(temp);
            n = temp;
        }
    }
    return true;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

1. 两数之和（经典哈希）

1. 两数之和

• 用对象{}来存某个值和它的下标

var twoSum = function (nums, target) {
    // key:值  value:下标
    let obj = {};
    for (let i = 0; i < nums.length; i++) {
        let find = target - nums[i];
        if (obj[find] !== undefined) {
            return [i, obj[find]];
        } else {
            obj[nums[i]] = i;
        }
    }
    return [];
};
1
2
3
4
5
6
7
8
9
10
11
12
13

454. 四数相加 II

454. 四数相加 II

一个map版：

var fourSumCount = function (nums1, nums2, nums3, nums4) {
    let map1 = new Map();

    for (let i of nums1) {
        for (let j of nums2) {
            let k = i + j;
            let kk = map1.get(k) ? map1.get(k) : 0;
            kk++;
            map1.set(k, kk);
        }
    }

    let ans = 0;
    for (let i of nums3) {
        for (let j of nums4) {
            let k = i + j;
            let find = 0 - k;
            let temp = map1.get(find) ? map1.get(find) : 0;
            ans += temp;
        }
    }

    return ans;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

两个map和forEach版：注意，forEach参数(value,key)

var fourSumCount = function (nums1, nums2, nums3, nums4) {
    let map1 = new Map();
    let map2 = new Map();

    for (let i of nums1) {
        for (let j of nums2) {
            let k = i + j;
            let kk = map1.get(k) ? map1.get(k) : 0;
            kk++;
            map1.set(k, kk);
        }
    }
    for (let i of nums3) {
        for (let j of nums4) {
            let k = i + j;
            let kk = map2.get(k) ? map2.get(k) : 0;
            kk++;
            map2.set(k, kk);
        }
    }

    let ans = 0;
    // 参数:先value后key
    map1.forEach((value, key) => {
        // value表示key出现的次数
        let find = 0 - key;
        if (map2.has(find)) {
            ans += value * map2.get(find);
        }
    })


    return ans;
};
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
27
28
29
30
31
32
33
34

15. 三数之和（双指针）

15. 三数之和

• 可以用哈希，但是会很麻烦
• 所以这里用双指针

思路：来自代码随想录

var threeSum = function (nums) {
    let ans = [];
    // 从小到大
    nums.sort((a, b) => a - b);
    if (nums[0] > 0) return ans;

    for (let i = 0; i < nums.length; i++) {
        let l = i + 1, r = nums.length - 1;
        if (i && nums[i] === nums[i - 1]) continue;
        while (l < r) {
            let sum = nums[i] + nums[l] + nums[r];
            if (sum > 0) r--;
            else if (sum < 0) l++;
            else {
                ans.push([nums[i], nums[l], nums[r]]);
                // 去重
                while (l < r && nums[l] === nums[l + 1]) {
                    l++;
                }
                while (l < r && nums[r] === nums[r - 1]) {
                    r--;
                }
                l++, r--;
            }
        }
    }

    return ans;
};
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
27
28
29

18. 四数之和（双指针）

18. 四数之和

var fourSum = function (nums, target) {
    let ans = [];
    const len = nums.length;
    if (len < 4) return ans;
    nums.sort((a, b) => a - b);

    for (let i = 0; i < len - 3; i++) {
        if (i && nums[i] === nums[i - 1]) continue;

        for (let j = i + 1; j < len - 2; j++) {
            if (j > i + 1 && nums[j] === nums[j - 1]) continue;

            let l = j + 1, r = len - 1;
            while (l < r) {
                let sum = nums[i] + nums[j] + nums[l] + nums[r];
                if (sum < target) {
                    l++;
                } else if (sum > target) {
                    r--;
                } else {
                    ans.push([nums[i], nums[j], nums[l], nums[r]]);

                    // 去重
                    while (l < r && nums[l] === nums[l + 1]) {
                        l++;
                    }
                    while (l < r && nums[r] === nums[r - 1]) {
                        r--;
                    }
                    l++; r--;
                }
            }
        }
    }

    return ans;
};
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
27
28
29
30
31
32
33
34
35
36
37

相关题目

是和主要题目类似的题目。

383. 赎金信

383. 赎金信

 var canConstruct = function(ransomNote, magazine) {
    // 如果magazine>=ransomNote true
    let array=new Array(26).fill(0);
    let base='a'.charCodeAt();

    // magazine
    for(let i of magazine){
        let num=i.charCodeAt()-base;
        array[num]++;
    }

    // ransomNote
    for(let i of ransomNote){
        let num=i.charCodeAt()-base;
        array[num]--;
    }

    let flag=0;
    array.forEach(function(item){
        if(item<0){
            flag=1;
        }
    })

    if(flag) return false;
    return true;
};
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
27

49. 字母异位词分组（Array，Map的运用）

49. 字母异位词分组

• 把每个字符串str转换为数组（Array.from）
• 数组排序，得到唯一的key
• 找到对应的value，添加当前的str
• 把最后的map转换为array
• 要熟练运用Array和Map

var groupAnagrams = function (strs) {
    const map = new Map();
    for (let str of strs) {
        // 把str字符串变成数组
        let array = Array.from(str);
        array.sort();
        // key:String
        let key = array.toString();
        // value:Array
        let value = map.get(key) ? map.get(key) : new Array();
        value.push(str);
        map.set(key, value);
    }

    return Array.from(map.values());
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

438. 找到字符串中所有字母异位词（滑动窗口）

438. 找到字符串中所有字母异位词

• 滑动窗口

var findAnagrams = function (s, p) {
    if (s.length < p.length) return [];

    var compare = function (ss, pp) {
        for (let i = 0; i < 26; i++) {
            if (ss[i] != pp[i]) {
                return false;
            }
        }
        return true;
    }

    // s长p短
    let pp = new Array(26).fill(0);
    let ss = new Array(26).fill(0);
    let ans = new Array();

    // j 慢指针
    let j = 0;

    // 计算p
    for (let char of p) {
        pp[char.charCodeAt() - 'a'.charCodeAt()]++;
    }

    const sl = s.length, pl = p.length;
    for (let i = 0; i < pl; i++) {
        let char = s[i];
        ss[char.charCodeAt() - 'a'.charCodeAt()]++;
    }

    if (compare(ss, pp)) {
        ans.push(0);
    }

    for (let i = pl; i < sl; i++, j++) {
        let char = s[i];
        ss[char.charCodeAt() - 'a'.charCodeAt()]++;
        char = s[j];
        ss[char.charCodeAt() - 'a'.charCodeAt()]--;
        if (compare(ss, pp)) {
            ans.push(j + 1);
        }
    }
    return ans;
};
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

350. 两个数组的交集 II

350. 两个数组的交集 II

var intersect = function (nums1, nums2) {
    let a1 = new Array(1001).fill(0);
    let a2 = new Array(1001).fill(0);

    for (let i = 0; i < nums1.length; i++) {
        a1[nums1[i]]++;
    }

    for (let i = 0; i < nums2.length; i++) {
        a2[nums2[i]]++;
    }

    let ans = new Array();

    for (let i = 0; i <= 1000; i++) {
        if (a1[i] && a2[i]) {
            let num = Math.min(a1[i], a2[i]);
            for (let j = 0; j < num; j++) {
                ans.push(i);
            }
        }
    }
    return ans;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24