代码随想录-哈希表

哈希表

哈希表，哈希表（英文名字为Hash table，国内也有一些算法书籍翻译为散列表）。

哈希表能解决什么问题呢，一般哈希表都是用来快速判断一个元素是否出现集合里。

要枚举的话时间复杂度是O(n)，但如果使用哈希表的话，只需要O(1)就可以做到。

当我们想使用哈希法来解决问题的时候，我们一般会选择如下三种数据结构。

数组
set （集合）： Set 是唯一值的集合。每个值在 Set 中只能出现一次。一个 Set 可以容纳任何数据类型的任何值。 Set对象的方法有add(),delete(),has(),forEach()…
map (映射) ：Map 对象存有键值对，其中的键可以是任何数据类型。Map 对象记得键的原始插入顺序。Map 对象具有表示映射大小的属性。

// Map对象的方法有为 Map 对象中的键设置值set(),获取 Map 对象中键的值(),返回键数据keys(),返回值数组values()，返回键值对数组entries()…

242.有效的字母异位词

方法一：数组实现

// 数组实现
var isAnagram = function(s, t) {
    // 长度不等，可以直接返回
    if(s.length !== t.length) return false;
    // 新建空数组
    const resSet = new Array(26).fill(0);
    // a的asc2码
    const base = "a".charCodeAt();
    for(const i of s) {
        // 这样写，26个英文字母都有它们的下标
        // resSet[]储存了26个英文字母出现的次数
        resSet[i.charCodeAt() - base]++;
    }
    for(const i of t) {
        // 判断是否是异位词：用字母i在s中出现的次数减去在t中出现的次数
        // !x是求反，只有x值是零才成立。
        // 只要t有一个字母的次数大于s，就返回假。
        // 由于已经事先判断过两个字符的总长度相等，所以不用再判断s某个字母在s中出现的次数大于t
        if(!resSet[i.charCodeAt() - base]) return false;
        resSet[i.charCodeAt() - base]--;
    }
    return true;
};

方法二：Map()实现

// Map()实现
var isAnagram = function(s, t) {
        // 长度不等，可以直接返回
    if(s.length !== t.length) return false;
    //Map是一个对象
    let map = new Map()
    for(const char of s){
        const times = map.get(char) || 0  //之前出现过几次
        map.set(char,times + 1)
    }
    for(const char of t){
        const times = map.get(char) || 0  //之前出现过几次
        map.set(char,times - 1)
    }
    for(let item of map){
        //item[1]代表出现次数，item[0]代表这个数字
        if(item[1] != 0){
            return false
        }
    }
    return true
};