哈希表经典汇总

1. 两数之和

方法一
两层循环暴力匹配

var twoSum = function (nums, target) {
  for (let i = 0, len = nums.length; i < len; i++) {
    for (let j = 0, leng = nums.length; j < leng; j++) {
      if (i !== j && nums[i] + nums[j] === target) {
        return [i, j]
      }
    }
  }
};

复杂度分析
时间复杂度：
对于每个元素，我们试图通过遍历数组的其余部分来寻找它所对应的目标元素，这将耗费的时间。因此时间复杂度为
空间复杂度：
方法二
哈希表

1. 把当前元素的位置存入哈希表，用目标值 - 当前元素值作为key，
2. 如果哈希表中找到key，则返回当前key指向的值和当前索引。

   var twoSum = function (nums, target) {
    const dict = new Map()
    for (let i = 0; i < nums.length; i++) {
        const ele = nums[i]
        if (dict[ele] !== undefined) { // ② 如果哈希表中找到值则返回哈希表中对应key的值和当前索引
            return [dict[ele], i]
        }
        dict[target - ele] = i // ① 把当前元素的位置存入哈希表，用目标值 - 当前元素值作为key
    }
   };
   

   时间复杂度：，
   我们把包含有 个元素的列表遍历两次。由于哈希表将查找时间缩短到 ，所以时间复杂度为。
   空间复杂度：，
   所需的额外空间取决于哈希表中存储的元素数量，该表中存储了个元素。

387. 字符串中的第一个唯一字符

方法一
indexOf和lastIndexOf
思路
如果一个字符在从头开始找和从尾开始找是同一个位置，则只出现了一次
如果第一个出现的位置和最后出现的位置是一个位置，就代表这个字符在这个字符串中只出现过一次
lastIndexOf
（https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Array/lastIndexOf）

/**
 * @param {string} s
 * @return {number}
 */
var firstUniqChar = function(s) {
    for(let i = 0; i < s.length; i++){
        if(s.indexOf(s[i]) === s.lastIndexOf(s[i])) return i
    }
    return -1
};

复杂度分析
时间复杂度：
外层遍历，时间复杂度为 ，调用 indexOf 的复杂度为 ，得出总的时间复杂度为
空间复杂度：
因为除了临时变量 i，没有开辟额外的空间
方法二
哈希表
思路
第一边循环存储哈希表，
第二遍循环找第一个是值是1的。

var firstUniqChar = function(s) {
    const dict = new Map()
    for(const iter of s){
        dict[iter] = dict[iter] === undefined ? 1 : 2
    }
    for(let i = 0; i < s.length; i++){
        if(dict[s[i]] === 1) return i
    }
    return -1
};

复杂度分析
时间复杂度：
因为有两次遍历，且每次遍历都只有一层没有嵌套，所以遍历的次数只和入参字符串 s 的长度线性正相关
空间复杂度：
因为变量只有 hash 和 i，开辟空间大小不随输入的变量变化

219. 存在重复元素 II

方法一
滑动窗口
维护了一个 大小的滑动窗口，然后在这个窗口里面搜索是否存在跟当前元素相等的元素。

public boolean containsNearbyDuplicate(int[] nums, int k) {
    for (int i = 0; i < nums.length; ++i) {
        for (int j = Math.max(i - k, 0); j < i; ++j) {
            if (nums[i] == nums[j]) return true;
        }
    }
    return false;
}
// Time Limit Exceeded.
作者：LeetCode
链接：https://leetcode-cn.com/problems/contains-duplicate-ii/solution/cun-zai-zhong-fu-yuan-su-ii-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

复杂度分析
时间复杂度：
每次搜索都要花费 的时间，哪怕 比 大，一次搜索中也只需比较 次。
空间复杂度：
方法二
哈希表
遍历数组，对于每个元素做以下操作：

• 在散列表中搜索当前元素，如果找到了就返回 true。
• 在散列表中插入当前元素。
• 如果当前散列表的大小超过了 ， 删除散列表中最旧的元素。

返回 false。

var containsNearbyDuplicate = function(nums, k) {
    const mSet = new Set();
    for(let i = 0; i < nums.length; i++) {
        if(mSet.has(nums[i])) return true;
        mSet.add(nums[i]);
        if(mSet.size > k) mSet.delete(nums[i - k]);
    }
    return false;
};

复杂度分析
时间复杂度：
我们会做 次 搜索，删除，插入 操作，每次操作都耗费常数时间。
空间复杂度：
开辟的额外空间取决于散列表中存储的元素的个数，也就是滑动窗口的大小

350. 两个数组的交集 II

方法一
哈希表
由于同一个数字在两个数组中都可能出现多次，因此需要用哈希表存储每个数字出现的次数。

1. 首先遍历第一个数组，并在哈希表中记录第一个数组中的每个数字以及对应出现的次数，
2. 然后遍历第二个数组，对于第二个数组中的每个数字，如果在哈希表中存在这个数字，则将该数字添加到答案，并减少哈希表中该数字出现的次数。

   var intersect = function (nums1, nums2) {
    const dict = new Map()
    const ans = []
    for (let i = 0; i < nums1.length; i++) {
        dict[nums1[i]] = dict[nums1[i]] === undefined ? 1 : dict[nums1[i]] += 1
    }
    for (let i = 0; i < nums2.length; i++) {
        if (dict[nums2[i]] > 0) {
            ans.push(nums2[i])
            dict[nums2[i]]--
        }
    }
    return ans
   };
   

   复杂度分析
   时间复杂度：
   两次遍历
   空间复杂度：
   开辟了一个哈希表，一个数组

554. 砖墙

方法一
哈希表
想象一下，把这个墙壁压成一条线，线的节点墙壁的空隙，会压成很多的节点，找重复节点最多的地方就是穿过最多的。

var leastBricks = function (wall) {
    const dict = new Map()
    let max = 0
    for (let i = 0; i < wall.length; i++) {
        let s = 0
        for (let j = 0; j + 1 < wall[i].length; j++) {
            s += wall[i][j]
            dict[s] = dict[s] !== undefined ? dict[s] += 1 : 1
            max = Math.max(max, dict[s])
        }
    }
    return wall.length - max
};

复杂度分析
时间复杂度：
两层遍历
空间复杂度：
压缩墙壁的节点

884. 两句话中的不常见单词

方法一
哈希表
题意就是在两个列表中找只出现一次的单词
一遍循环统计单词个数
一遍循环找出现一次的

var uncommonFromSentences = function(A, B) {
    const list = A.split(' ').concat(B.split(' '))
    const dict = new Map()
    list.forEach(item => {
        dict[item] = dict[item] !== undefined ? 2 : 1
    })
    const res = []
    for(let prop in dict){
        if(dict[prop] === 1){
            res.push(prop)
        }
    }
    return res
};

复杂度分析
时间复杂度：
两个for循环
空间复杂度：
一个字典

总结

用哈希表主要是用哈希表计数和快速查找

参考

政采云算法小册
https://101.zoo.team/zi-fu-chuan/zi-fu-chuan-part-2-bao-shu-fan-zhuan-zi-fu-chuan-he-zi-fu-chuan-zhong-de-di-yi-ge-wei-yi-zi-fu#zi-fu-chuan-zhong-de-di-yi-ge-wei-yi-zi-fu
leetcode官网答案
https://leetcode-cn.com/problems/two-sum/solution/liang-shu-zhi-he-by-leetcode-2/