哈希表有技术的功能，如果题目中有 至多xx次 至少xx次 唯一 等字眼，可以联想到用哈希表来解决。

例如：存在重复元素

给定一个整数数组，判断是否出现重复元素

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

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

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
  const map = new Map();
  let result = false;
  for (let i = 0; i < nums.length; i++) {
    if (map.has(nums[i]))  {
      result = true
      break
    } else {
      map.set(nums[i], 1)
    }
  }
  return result
};

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

一看题目，唯一，技术题，map走起

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

s = "leetcode"
返回 0
s = "loveleetcode"
返回 2

/**
 * @param {string} s
 * @return {number}
 */
var firstUniqChar = function(s) {
  const arr = s.split('')
  const map = new Map()
  const length = arr.length
  for (let i = 0; i < length; i++) {
    if (map.has(arr[i])) {
      map.set(arr[i], map.get(arr[i]) + 1) // 每出现一次就加1
    } else {
      map.set(arr[i], 1)
    }
  }
  let index = -1
  for (const [key, value] of map) {
    if (value === 1) {
      index = arr.indexOf(key)
      break // 找到第一个之后就退出，不必再找
    }
  }
  return index
}

上面使用Map来计数，用普通对象当然也可以。

var firstUniqChar = function (s) {
    const map = {}
  for (let key of s) map[key] = (map[key] || 0) + 1 // for of 字符串
  const length = s.length
  for (let i = 0; i < length; i++) {
        if (map[s[i]] === 1) return i // 直接退出方法
    }
  return -1
}

有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

示例 1:
输入: s = "anagram", t = "nagaram" 输出: true
示例 2:
输入: s = "rat", t = "car" 输出: false
提示:
1 <= s.length, t.length <= 5 * 104
s 和 t 仅包含小写字母

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function(s, t) {
  if (s.length !== t.length) return false // 如果长度不等，必然不是字母异位词
  const map1 = new Map()
  const map2 = new Map()
  for(let i of s) map1[i] = (map1[i] || 0) + 1
  for(let i of t) map2[i] = (map2[i] || 0) + 1
  const length1 = Object.keys(map1)
  for (let key of length1) {
    if (!map2[key] || map2[key] !== map1[key]) return false
  }
  return true
};

多数元素

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

可以排序，然后中间那个数，肯定是多数元素。
也可以计数，哈希map搞起。 ```javascript 示例 1：输入：[3,2,3] 输出：3

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

```javascript
/**
* 时间复杂度: O(n) 遍历一次,空间复杂度: O(n) obj中属性最多为 n/2 个
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
  const map = {}
  for (let key of nums) map[key] = (map[key] || 0) + 1 // 更优雅
  for (let key of Object.keys(map)) {
    if (map[key] > (nums.length >> 1)) return key // 因为必然存在，则有且仅有一个多数元素
  }
};

也可以使用栈方法。栈方法在这种找多数元素的场景下还是蛮有代表性的。

思路为：

当元素和栈顶元素相等或栈为空时入栈，否则出栈。这样到最后肯定只剩下多数元素了。

// 时间 O(n) 循环一次nums 空间 O(n)
var majorityElement = function(nums) {
  const length = nums.length
  const stack = []
  for (let i = 0; i < length; i++) {
      if (!stack.length || stack[0] === nums[i]) {
        stack.push()
    } else {
        stack.pop()
    }
  }
  return stack[0]
};

分治算法。仔细体会。

解题思路：
如果a是数组nums的众数，那么如果我们把nums分成两部分，a必然是至少一部分的众数。
分：将数组分成左右两个部分。
解：分别求出左半部分的众数a1和右半部分的众数a2。
合：在a1 和 a2 中选出正确的众数。

var majorityElement = function(nums) {
    function majorElementRec(nums, l, r) {
    // r是length - 1, 左右相等，只有一个元素
      if (l === r) return nums[l] // 进行最后一次递归时，这里直接返回，退出了递归，让最后一次调用majorElementRec的left和right有了返回值。然后left和right 进行下面的计算，再返回，再让上面一层的left和right有了值，再继续这个循环。
    const mid = (r - l) >> 1
    const left = majorElementRec(nums, l, mid) // 递归调用，
    const right = majorElementRec(nums, mid+1, r)
    if (left === right) return left
    const leftCount = countInRange(nums, left, l, r)
    const rightCount = countInRange(nums, right, l, r)
    return leftCount > rightCount ? left : right // 那个重复的多用哪个
  }
  // 计算在区间中重复了几次
  function countInRange (nums, num, l ,r) {
      let count = 0;
    for (let i = 0; i < nums.length; i++) {
        if (num[i] === num) {
          count += 1
      }
    }
    return count
  }
  return majorElementRec(nums, 0, nums.length - 1)
}

进阶：

尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

前面开辟了一个新的存储空间, 生成了一个map对象，其空间复杂度为O(n)，如果要设计时间复杂度为O(n), 空间复杂度为O(1), 就是说只能开辟一个基础类型的空间。

抵消法（Boyer-Moore 投票算法）：相同的加1，不同的减1，存在多数元素，最后肯定剩下大于一半的那个数.

其实跟栈方法思路是一致的，是栈的降维化方法。

// 时间复杂度为 O(n)、空间复杂度为 O(1) 
var majorityElement = function(nums) {
    let candidate;
  let count = 0;
  for (let n of nums) {
      if (count === 0) candidate = n
    if (n === candidate) {
        count += 1
    } else {
        count -= 1
    }
  }
  return candidate
}

只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

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

当然是可以利用map计数的，但是使用了额外空间。这里由于数组的特殊性，可以使用异或^运算。

// 利用异或^。
// 任何数跟自己异或 ，结果是0
// 任何数跟0做异或，结果是本身
// 异或满足交换律和结合律
var singleNumber = function(nums) {
  let res;
  for(let i = 0; i < nums.length; i++) {
    res = res^nums[i]
  }
  return res
};

位1的个数

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。

示例 1：
输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
示例 2：
输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
示例 3：
输入：11111111111111111111111111111101
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。

转字符串过滤、转字符串变数组，然后每个元素数字在跟1异或都可以。但是有更快的数学方法
对于一个二进制数来说，每次执行
x = x & (x - 1), 会将x用二进制表示的左最右边的1变为0 (是最右边的1，不是最右一位)
例如 56的二进制 111000
55 的二进制 110111
(56 & 55) 的二进制 110000, 也就是56二进制表示里的最右边的1变成了0。
利用这个数学特性，可以进行如下算法。

/**
 * @param {number} n - a positive integer
 * @return {number}
 */
var hammingWeight = function(n) {
    let count = 0;
    while(n) {
      n = n & (n - 1)
      count++
    }
    return count
};

📖 算法积累

至多、至少、唯一（8题）（利用哈希表）

给定一个整数数组，判断是否出现重复元素

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

有效的字母异位词

多数元素

只出现一次的数字

位1的个数

至多、至少、唯一 （8题）（利用哈希表）

给定一个整数数组，判断是否出现重复元素

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

有效的字母异位词

多数元素

只出现一次的数字

位1的个数

至多、至少、唯一（8题）（利用哈希表）