您现在的位置是：首页 >其他 >leetcode刷题之哈希表相关问题js网站首页其他

242.有效的字母异位符

方法一：使用两个map对象来保存

时间复杂度:O(n) 空间复杂度O(n)

var isAnagram = function(s, t) {
    if(s.length!==t.length) return false //如果长度不等，那么一定不满足要求
    //分别对字符串s t进行遍历，然后分别使用map对象进行保存
    let map1 = new Map()
    let map2 = new Map()
    //字符串是可迭代的，可以使用for of进行遍历
    for(let item of s){
        map1.set(item,map1.get(item)+1||1)
    }
    for(let item of t){
        map2.set(item,map2.get(item)+1||1)
    }
    //第三个循环 使用for of从map1中拿key，然后对map2中的进行比较
    for(let [key,val] of map1){
        //注意，当map1中的所有的属性所对应的值都和map2中的相等的时候，不存在map2中比map1多一个属性的情况
        if(!map2.get(key)||map2.get(key)!==val){
            return false
        }
    }
    return true
};

方法二：使用一个map

var isAnagram = function(s, t) {
    //使用一个map对象
    let map = new Map()
    for(let val of s){
        map.set(val,map.get(val)+1||1)
    }
    //然后遍历t，从map中进行相减
    for(let key of t){
        //map中没有这个键
        if(!map.has(key)) return false
        map.set(key,map.get(key)-1)
        if(map.get(key)==0) map.delete(key)
    }
    if(map.size==0) return true
    return false
};

349.两个数组的交集

方法一：set+map+for of

var intersection = function(nums1, nums2) {
    //时空复杂度都是O(n)
    //使用一个map对象来保存num1中的每一个键，然后使用arr保存两者间的相同的
    let map = new Map()
    let arr = []
    for(let val of nums1){
        map.set(val,map.get(val)+1||1)
    }
    for(let val of nums2){
        if(map.has(val)){
            arr.push(val)
        }
    }
    //set进行去重，然后再将对象转换为数组
    return Array.from(new Set(arr))
};

方法二：只是用set

时空都是O(n)
new Set()毫无疑问是O(n)
Array.from()也是O(n),原因见第三条:

var intersection = function(nums1, nums2) {
    let a = new Set(nums1)
    let b = new Set(nums2)
    return [...a].filter(item =>b.has(item))
};