【前端算法入门】哈希表（一）

文章目录 前言一、先来个两个简单题1.存在重复元素【简单】2.字符串中的第一个唯一字符【简单】 二、进阶3.多数元素 【中等】4.只出现一次的数字 总结

---

前言

我前几天写了一篇文章，《JS数组去重到底有几种方法？》，有两三种方法的去重思路用到了哈希表概念，那么哈希表在算法中可以解决什么问题呢？可太多了朋友们。今天这篇文章先来盘一盘哈希表在一些计数的算法场景中的应用。

---

一、先来个两个简单题 1.存在重复元素【简单】

题目描述如下：

给定一个整数数组，判断是否存在重复元素。
如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。

示例 1:
输入: [1,2,3,1]
输出: true

示例 2:
输入: [1,2,3,4]
输出: false

解决思路：
我们遍历数组时，经过数组中的每一项就往map中添加，比如[1,2,3,1]

第一项：遍历到第一个1时，对象返回{ 1: 1 },代表1出现1次
第二项：遍历到2时，返回 { 1: 1, 2: 1 }
第三项：遍历到3时，返回 { 1: 1, 2: 1， 3: 1 }
第四项：遍历到第二个1时，发现原来的对象里已经有1了，返回true，否则最后返回false

代码这不就顺手写出来了

const containsDuplicate = function(nums) {
    let map = new Map();
    for(let i of nums){
        if(map.has(i)){
            return true;
        }else{
            map.set(i, 1);
        }
    }
    return false;
};

再来一道，接着练

2.字符串中的第一个唯一字符【简单】

题目如下：
给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。

示例：
s = "leetcode"
返回 0

s = "loveleetcode"
返回 2
 
// 提示：你可以假定该字符串只包含小写字母

解题思路：
一看题目，唯一，条件反射，这还是记数题啊，map走起！
第一步：遍历字符串
第二步：用一个对象{}来记数，出现过一次就+1，
第三步：遍历完毕，再次遍历字符串，看它们在之前记录的对象里的值，是否是1，是就返回下标，不是返回-1。

代码这不也是顺手就写出来了

var firstUniqChar = function(s) {
  const map = {};
  for(let v of s) map[v] = (map[v] || 0) + 1;
  for(let i = 0; i < s.length; i++) if(map[s[i]] === 1) return i;
  return -1;
};

二、进阶 3.多数元素 【中等】

题目如下：
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：
输入：[3,2,3]
输出：3

示例 2：
输入：[2,2,1,1,1,2,2]
输出：2

解题思路：
看题目，有次数两个字，接着条件反射，这还是记数题啊，map继续走起！

1.声明一个计数器,也就是一个对象const map = {}
2.遍历字符串，开始记数，如果字符串的字母第一次碰见，map[第一次碰见的字母] = 1
3.如果map已经记录过这个字母，则map[记录过的的字母] += 1
4.在遍历的过程中，看map[记录过的的字母] 是否大于 数组总长度/2

var majorityElement = function(nums) {
  const map = {}
  const n = nums.length >> 1 // >>是右移运算符，意思是除以2
  for(let i = 0; i < nums.length; i++){
      map[nums[i]] = map[nums[i]] !== undefined ? map[nums[i]] + 1 : 1
      if(map[nums[i]] > n) return nums[i]
  }
}

是不是so easy 来吧 自测一道

4.只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

示例 1:
输入: [2,2,1]
输出: 1

示例 2:
输入: [4,1,2,1,2]
输出: 4

大家想想，答案等我下次更

---

总结

如果大家看完题目就立马有了解题思路，那么恭喜你，你已经掌握了这一类算法题了。如果还有点吃力那就收藏这篇文章多看两遍， 哈希表在其他方面的应用等我这两天抽空更，欢迎大家关注，我们一起学习一起进步!