leetcode每天5题-Day32

上一篇文章中说了数组可以作为哈希结构，但 如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费！

1.两个数组的交集

349. 两个数组的交集-简单
b站视频-代码随想录
自己写的👇
定义了两个set，分别给两个数组去重，然后两个set取交集，最后交集的值给数组ans

var intersection = function(nums1, nums2) {
    const set = new Set();
    const set1 = new Set();
    for(const num1 of nums1){
        set.add(num1);
    }
    for(const num2 of nums2){
        set1.add(num2);
    }

    const ans = [];
    // 两个set取交集
    let newset = new Set([...set].filter(x=>set1.has(x)));
    for(const num2 of newset.keys()){
            ans.push(num2);
    }
    return ans;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

简洁版

var intersection = function(nums1, nums2) {
    const set1 = new Set();
    for(const num2 of nums2){
        set1.add(num2);
    }
    return Array.from(new Set(nums1.filter(x=>set1.has(x))));
};
1
2
3
4
5
6
7

代码随想录版

var intersection = function(nums1, nums2) {
    // 根据数组大小交换操作的数组
    if(nums1.length < nums2.length) {
        const _ = nums1;
        nums1 = nums2;
        nums2 = _;
    }
    const nums1Set = new Set(nums1);
    const resSet = new Set();
    // for(const n of nums2) {
    //     nums1Set.has(n) && resSet.add(n);
    // }
    // 循环 比 迭代器快
    for(let i = nums2.length - 1; i >= 0; i--) {
        nums1Set.has(nums2[i]) && resSet.add(nums2[i]);
    }
    return Array.from(resSet);
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

数组作哈希👇①

var intersection = function(nums1, nums2) {
    const hash = new Array(1005).fill(0);
    for(const num1 of nums1){
        hash[num1] = 1;
    }
    const set = new Set();
    for(const num2 of nums2){
        if(hash[num2] == 1){
            set.add(num2);
        }
    }
    return Array.from(set);
};
1
2
3
4
5
6
7
8
9
10
11
12
13

数组作哈希👇②

var intersection = function(nums1, nums2) {
    const hash = new Array(1005).fill(0);
    for(const num1 of nums1){
        hash[num1] = 1;
    }

    const ans = [];
    for(const num2 of nums2){
        if(hash[num2] == 1 && ans.indexOf(num2) === -1){
            ans.push(num2);
        }
    }
    return ans;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

2.两个数组的交集 II

350. 两个数组的交集 II-简单
①哈希表
用map统计nums1中每个数字出现的频率，当map中有nums2中的数字时，把该数字放进数组ans中并使map中该数字的频率减一

var intersect = function(nums1, nums2) {
    const map = new Map();
    for(const num1 of nums1){
        map.has(num1)?map.set(num1,map.get(num1)+1):map.set(num1,1);
    }
    const ans=[];
    for(const num2 of nums2){
        if(map.has(num2) && map.get(num2) > 0){
            ans.push(num2);
            map.set(num2,map.get(num2)-1);
        }
    }
    return ans;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

力扣官方👇

②排序+双指针

var intersect = function(nums1, nums2) {
    nums1.sort((a,b) => a-b);
    nums2.sort((a,b) => a-b);
    const ans = [];
    let i = 0,j = 0;
    // 注意此处是 && 而不是 ||  因为当其中一个数组的指针遍历完成时 那么整个遍历就结束了 
    while(i < nums1.length && j < nums2.length){
        if(nums1[i] === nums2[j]){
            ans.push(nums1[i]);
            i++;
            j++
        }else if(nums1[i] > nums2[j]){
            j++;
        }else{
            i++;
        }
    }
    return ans;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

力扣官方👇

3.快乐数

202. 快乐数-简单
快乐数一点都不快乐…提交这个题费了我老鼻子劲儿，一直找不出来自己哪错了，折腾了快一个小时，感觉代码没问题，也和答案对比了，就是没看出来为什么有错，被自己气到胃疼…
看别人的代码都是把更新sum这一操作放在一个函数里了，我以为是不能我这样写，得放在函数才行，最后不死心，又看了眼我的代码，才发现忘了更新sum的值，每次循环之前sum的值每次都要重置为0…又是被自己蠢哭的一天

var isHappy = function(n) {
    const set = new Set();
    set.add(n);
    let sum = 0;
    while(n !== 1){
        while (n>0) {
            sum += (n % 10) ** 2
            n = Math.floor(n / 10)
        }
        n = sum;
        // 不更新sum  sum的值就会越来越大...
        sum = 0;
        if(set.has(n)){
            return false;
        }else{
            set.add(n);     
        }
    }
    return true;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

这道题还有很多解法，快慢指针、环形链表等，改天再看吧，今天太不快乐了，希望下次再看快乐数时我会很快乐。

4.两数之和

1. 两数之和-简单
b站视频-代码随想录

什么时候使用哈希法：当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。

使用数组和set来做哈希法的局限：

• 数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
• set是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下标位置，因为要返回x 和 y的下标。所以set 也不能用。

思路：用map存放我们遍历过的元素，map的key为元素值，value为下标

var twoSum = function(nums, target) {
    const map = new Map();
    for(let i = 0;i < nums.length;i++){
        let num = target - nums[i];
        if(map.has(num)){
            return [map.get(num),i];
        }else{
            map.set(nums[i],i);
        }
    }
    return [];
};
1
2
3
4
5
6
7
8
9
10
11
12

let hash = {};

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

代码随想录👇

5.四数相加 II

454. 四数相加 II-中等
b站视频-代码随想录
思路：若先遍历一个数组，再遍历三个数组，则时间复杂度为O(n^3)。先遍历前两个数组，再遍历剩下两个数组，就可以将时间复杂度降为O(n ^2)。

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
20

注：count每次不是加1，而是加上目标值在map中出现的次数。