代码随想录day06【 哈希表】有效的字母异位词 两个数组的交集 快乐数 两数之和

哈希表

使用情况：用来快速判断一个元素是否出现集合里。
例如查询一个名字是否在这所学校里。枚举：时间复杂度是O(n)，哈希表：O(1)

有效的字母异位词

题目：https://leetcode.cn/problems/valid-anagram/

//时间复杂度：O(n)
function isAnagram(s, t) {
  let map1 = createMap(s);
  let map2 = createMap(t);

  let arr = [...new Set((s + t).split(""))];
  for (let item of arr) {
    if (map1.get(item) !== map2.get(item)) {
      return false;
    }
  }
  return true;
}

function createMap(str) {
  let map = new Map();
  str.split("").forEach((item) => {
    if (map.has(item)) {
      map.set(item, map.get(item) + 1);
    } else {
      map.set(item, 1);
    }
  });
  return map;
}

两个数组的交集

题目：https://leetcode.cn/problems/intersection-of-two-arrays/

//法一：暴力法 时间复杂度：O(n2)
var intersection = function(nums1, nums2) {
    let ns1 = [...new Set(nums1)]
    let ns2 = [...new Set(nums2)]
    let res = []
    ns1.forEach(item=>{
        if(ns2.indexOf(item)>-1){
            res.push(item)
        }
    })
    return res
};

//法二：哈希表法 时间复杂度：O(n)
let map = new Map()
    let res =[]
    nums1.forEach(ele=>{
        if(!map.has(ele)){
            map.set(ele,ele)
        }
    })
    nums2.forEach(ele=>{
        if(map.has(ele)){
            res.push(ele)
        }
    })
    return [...new Set(res)]

快乐数

题目：https://leetcode.cn/problems/happy-number/
思路：数字最后都会进入循环

//时间复杂度：O(n)
var isHappy = function(n) {
    const getNext=(n)=>{
        let totalSum = 0;
        while(n>0){
            let d = n %10;
            n=parseInt(n/10);
            totalSum +=d*d
        }
        return totalSum
    }

    let map = new Map()
    while(n!==1 && !map.has(n)){
        map.set(n,true)
        n=getNext(n)
    }
    return n===1
};

两数之和

题目：https://leetcode.cn/problems/two-sum/

//法一：暴力法 时间复杂度：O(n2)
var twoSum = function(nums, target) {
   let nums2 = [...nums]
   for(let i=0;i<nums.length;i++){
       for(let j=i+1;j<nums2.length;j++){
           if(nums[i]+nums2[j] === target){
               return [i,j]
           }
       }
   }
};

//法二：哈希表 时间复杂度：O(n)
var twoSum = function(nums, target) {
   let map=new Map()
   for(let i in nums){
       let num = target-nums[i]
       if(map.has(num)){
           return [i,map.get(num)]
       }else{
           map.set(nums[i],i)
       }
   }
   
};