LeetCode Hot100-哈希

1.TypeScript - Map 对象(映射)

• Map 是 JavaScript 内置的哈希表实现：ES6 引入的 Map 类型本质上是一个基于哈希的键值对数据结构。

• Map 对象特点：Map([])保存键值对，键值对保存原始插入顺序，任意值可以作为key/键唯一，有大小可迭代

let map = new Map([

     ["key1","value1"], ["key2","value2"],...["keyN","valueN"]

])
/* Map 图示 */

+---------------------+
|       Map           |
+---------------------+
| [[Entries]]:        |
|   0: {"name" => "Alice"} 
|   1: {{id:1} => "obj"} 
| size: 2             |
+---------------------+

/*常见Map api, O(1) 时间复杂度的查找/插入和删除操作*/

//创建Map
const map = new Map();

// 设置键值对，返回该 Map 对象
map.set('name', 'Alice');
map.set(1, 'number one');
map.set({id: 1}, 'object key');

// 获取元素，返回键对应的值，如果不存在则返回 undefined
map.get('name')

// 检查键是否存在，返回一个布尔值
map.has('name')

// 删除元素，返回bool值
map.delete('name');

// 获取大小
console.log(map.size); // 2

// 清空Map
map.clear();

// 遍历Map
map.forEach((value, key) => {
  console.log(`${key}: ${value}`);
});

// 或者使用for...of
for (const [key, value] of map) {
  console.log(key, value);
}

2.两数之和

整数数组nums中找到数组和为target的两个元素index返回

题解思路：

• 创建hashMap，key 为 nums[i]，value 为index
• 遍历数组nums，若map中存在 target - nums[i] 目标数则返回下标[map.get(target - nums[i]),i]，不存在则添加当前entry map.set(nums[i],i)

var twoSum = function(nums, target) {
    let map = new Map()
    for(let i=0, len=nums.length;i<len;i++){
        if(map.has(target - nums[i])){
            return [map.get(target - nums[i]),i]
        }else{
            map.set(nums[i],i)
        }
    }
    return []
};

3.字母易位词分组

字符串数组strs中字母排序后相同的字符串以数组形式输出

题解思路：

• 将每个字符串排序，易位词排序后相同。
• 创建hashmap，key 为排序后易位词，value 为未排序字符串数组
• 遍历数组strs，易位词为key，添加当前字符串

var groupAnagrams = function(strs) {
    const m = new Map();
    for (const s of strs) {
        // 把 s 排序，作为哈希表的 key
        const sortedS = s.split('').sort().join('');
        if (!m.has(sortedS)) {
            m.set(sortedS, []);
        }
        // 排序后相同的字符串分到同一组
        m.get(sortedS).push(s);
    }
    // 哈希表的 value 保存分组后的结果
    return Array.from(m.values());
};

4. JavaScript - Set 对象(集合)

• Set 是 JavaScript 内置的哈希表实现：ES6 引入的 Set 类型本质上是一个基于哈希的集合数据结构。

• Set 对象特点：Set([])存储唯一值是value的集合，自动去重，值保存原始插入顺序，任意类型做值/value值唯一，有大小可迭代

let set = new Set([

  "value1","value2",..."valueN"

]);

/* Set 图示 */

+-----------------------+
|        Set            |
+-----------------------+
| size: 4               |
+-----------------------+
| [[Entries]]           |
|   0: 1                |
|   1: "text"           |
|   2: {name: 'John'}   | <-- 第一个对象
|   3: {name: 'John'}   | <-- 第二个独立的对象(地址值不同)
+-----------------------+

/*常见Map api, O(1) 时间复杂度的查找/插入和删除操作*/

// 创建set
const set = new Set();

// 添加元素,返回set对象
set.add(1);
set.add('text');
set.add({name: 'John'});

// 检查值是否存在，返回bool值
set.has(1) // true

// 删除元素，返回bool值
set.delete(1);

// 获取大小
set.size

// 清空Set，返回undefined
set.clear();

// 遍历Set
set.forEach(value => {
  console.log(value);
});

// 或者使用for...of
for (const value of set) {
  console.log(value);
}

5. 最长连续序列

未排序的整数数组nums中找到最长的连续数组，返回长度

解题思路：

• 排序时间复杂度为O(nlogn)超时，转为查询hashTable，set去重避免重复查找
• 遍历set哈希表，set.has(x-1)是否存在找到序列头第一个数，set.has(y)找到最后一个连续的数，循环结束y值为最大数+1，返回长度 y-x 为连续数组长度

var longestConsecutive = function(nums) {
    let ans = 0;
    const st = new Set(nums); // 把 nums 转成哈希集合
    for (const x of st) { // 遍历哈希集合
        if (st.has(x - 1)) {
            continue;
        }
        // x 是序列的起点
        let y = x + 1;
        while (st.has(y)) { // 不断查找下一个数是否在哈希集合中
            y++;
        }
        // 循环结束后，y-1 是最后一个在哈希集合中的数
        ans = Math.max(ans, y - x); // 从 x 到 y-1 一共 y-x 个数
    }
    return ans;
};