哈希表
哈希表
  理论基础
    什么是哈希表
      哈希表是根据关键码的值而直接进行访问的数据结构
      数组就是一张哈希表
        关键码就是数组的索引下标，通过下标直接访问数组中的元素
    解决问题
      快速判断一个元素是否出现在集合里
      牺牲空间换时间
        要使用额外的数组或 map 才能实现快速查找
    Go 中常用的哈希结构
      数组
        数据量小，数据跨度不大时使用
      map（映射）
        数据量大、散时使用，空间消耗大
    哈希函数
      将元素映射到哈希表上就涉及到了哈希函数 hash function
      hashFunction = hashCode(name) % tableSize
        保证索引落在 [0, tableSize - 1] 范围内
    哈希碰撞
      元素数量大于哈希表的大小，就算哈希函数计算再均匀，也会有一些元素同时映射到哈希表的同一个索引下标位置，这就用到了哈希碰撞。
      拉链法
        发生冲突的元素被存在链表中
        选择适当的哈希表大小
          数据规模 dataSize
          哈希表的大小 tableSize
          装载因子
            如果 α 太小（比如0.1），说明哈希表太大，大部分位置是空的，浪费内存
            如果 α 太大（比如2.5），说明数据比表大很多 -> 冲突频繁、链表过长或探测次数过多 -> 查找效率下降
            一般希望 α == 0.75，超过阈值就会扩容
      线性探测法
        tableSize 必须大于 dataSize
          依靠哈希表中的空位来解决碰撞问题
        开放寻址法
          如果某个位置被占用了，就顺着数组往后一个一个位置找，直到找到空位为止。
        插入过程
          先检查 hash(x) % tableSize 的位置是否空着
            空 -> 放入数据
            被占用 -> 继续向后找
              (h(x)+1) % tableSize, (h(x)+2) % tableSize, ...
              计算公式
                最终位置 = ( h(x) + i ) mod tableSize
                i 是探测次数（0，1，2，...）
        查询过程
          计算 (h(x)+1) % tableSize
          当前位置是目标元素 -> 查询到元素
          如果当前位置不是目标元素
            继续向后探测
              (h(x)+1) % tableSize, (h(x)+2) % tableSize, ...
              找到目标
              遇到空槽，说明不存在
        删除问题
          1. 把删除的位置标记为“已删除”，查询时会继续向后探测
          2. 删除元素后，将其后面的元素重新确定位置 (rehash)
          删除时不能简单地把位置清空，否则查询时可能会提前停止导致查询失败
  242.有效的字母异位词
    题意
      给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
      示例 1: 输入: s = "anagram", t = "nagaram" 输出: true
示例 2: 输入: s = "rat", t = "car" 输出: false
      字符串只包含小写字母。
s 和 t 是相同的单词也算做字母异位词
    数组
      只有26个字母，遍历 s 每个 rune - ‘a’ ，就可以用数组 record 下标 0 - 25 记录26个小写字母，每出现一次，value++
      遍历 t ，每查询到字母一次，value--
      record 数组中如果有元素不为 0 ，说明 s 和 t 的字母一定不相同
  349.两个数组的交集
    题意
      给定两个数组，编写一个函数来计算他们的交集
      要求去重，不考虑输出结果顺序
      1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000
    数组
      数组长度和元素都小于1000，可以用数组
      将 nums1 元素存入 hash 数组的下标，出现过的元素，下标对应数组的值为1，没出现的为0（实现去重）
      用 nums2 中的元素去查询 hash，查到了 1 就把元素放入 result，顺便把 hash 对应的值改为0，实现去重
    哈希表
      用 map 模拟 set
        set := make(map[int]struct{}, 0)
        set[v] = struct{}{}
          struct{}
            是类型，表示一个“没有字段的结构体类型”，也叫做 空结构体类型
          struct{}{}
            是值，表示一个该类型的零值字面量
          不用 bool 的原因
            语义上不关心值本身
            空结构体不占用任何空间，bool 占用更多空间
            map[int]struct{} 是 go 社区的约定，是模拟集合的惯用写法
      nums1 的值存入 set 中，遍历 nums2，如果 v 在 set 中存在，就把 v 加入结果 res 并 delete(set, v)
      return res
  202.快乐数
    题意
      编写一个算法来判断一个数 n 是不是「快乐数」
        如果是就返回 true，不是则返回 false
      「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。
      示例
        输入：19
输出：true
解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1
    思路
      题中提到会无限循环，也就是求和过程中 sum 会重复出现
      用哈希表 map 来判断 sum 是否出现过
        sum 出现过， 不是快乐数
          false
        没出现且 n == 1，是快乐数
          true
      难点：求和的过程
        从个位开始往高位求
        func getSum(n int) int {
sum := 0
for n > 0 {
sum += (n % 10) * (n % 10)
n = n / 10
}
return sum
}
  1.两数之和
    题意
      给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
      可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
      示例
        给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
    思路
      map
        key 存元素
        value 存下标
        在 key 中找 b (target - a)，从而找到 value 下标
        返回 [a_index, b_index] 或 nil
  454.四数相加II
    题意
      给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。
      为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -2^28 到 2^28 - 1 之间，最终结果不会超过 2^31 - 1 。
      示例
        输入:
          A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]
        输出:
          2
        解释:
          两个元组如下:
          (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
          (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
    思路
      由于这道题是四个独立的数组，只要找到 A[i] + B[j] + C[k] + D[l] = 0 即可。
不用考虑有重复的四个元素相加等于0的情况， 0+0+0+0 = 0 也可以。
      哈希表
        counter
          统计满足要求的元组总数
        map
          嵌套for遍历数组A和B
          key
            两数之和 a+b
          value
            a+b 出现次数
        嵌套for遍历数组C和D
          查询 0-(c+d) 在map中是否出现过
            出现 -> counter++
        return counter
      为什么不是先遍历 A 再遍历 B、C、D ？
        两两遍历，时间复杂度是 n^2
        先遍历A再BCD，时间复杂度是 n^3
  383.赎金信
    题意
      给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
        如果可以，返回 true ；否则返回 false 。
      提示
        ransomNote 和 magazine 由小写英文字母组成
        magazine 中的每个字符只能在 ransomNote 中使用一次。
        1 <= ransomNote.length, magazine.length <= 10^5
      示例
        canConstruct("a", "b") -> false
        canConstruct("aa", "ab") -> false
        canConstruct("aa", "aab") -> true
    思路
      和 242.有效的字母异位词 类似
        242
          求 a 和 b 是否可以相互组成
        本题
          求 a 能否组成 b
            不用考虑 b 能否组成 a
      数组
        26个小写字母，想到用数组。
        遍历 magazine 存入数组 record
          数组索引
            存字母
              rune - ‘a'
              0-25存26个小写字母
          数组value
            存字母的出现次数
        遍历 ransomNote ， record 中对应的字母--
          对应值小于0，说明ransomNote里出现的字符，magazine没有
          遍历结束，return true
  15.三数之和
    题意
      给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
      输出的顺序和三元组的顺序并不重要
        意思是可以排序
      示例
        示例1
          输入：nums = [-1,0,1,2,-1,-4]
          输出：[ [-1,-1,2], [-1,0,1] ]
          解释：
            nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
            nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
            nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
            不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
            注意，输出的顺序和三元组的顺序并不重要。
        示例 2
          输入：nums = [0,1,1]
          输出：[]
          解释：唯一可能的三元组和不为 0 。
        示例 3
          输入：nums = [0,0,0]
          输出：[[0,0,0]]
          解释：唯一可能的三元组和为 0 。
    思路
      这题不太适合用哈希表写，推荐用双指针法
      双指针
        排序
          顺序不重要，说明可以排序，先对数组排序
        for循环，i 从 0 开始，
定一个下标 left 在 i+1，right 在 len-1
          可以判断 nums[i] > 0 就break 然后 return result。因为 a>0 , a+b+c 一定大于0，不等于0
          去重
        移动 left 和 right
          如果 nums[i] + nums[left] + nums[right] > 0
            三数之和大了，right向左移动
          如果 nums[i] + nums[left] + nums[right] > 0
            三数之和小了，left向右移动
          如果 nums[i] + nums[left] + nums[right] == 0
            收集一次三元组结果，开始去重
        去重逻辑
          考虑三个数的去重。 a, b ,c, 对应的就是 nums[i]，nums[left]，nums[right]
          a 去重
            判断 nums[i] 与 nums[i-1] 是否相同
              和 nums[i[ 比较它的前一个
              if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
              为什么不是比较它的后一个？
                如果比较后一个
if (nums[i] == nums[i + 1]) { // 去重操作
continue;
}
会漏掉三元组中出现重复元素的情况，
                例如{-1, -1 ,2} 这组数据，当遍历到第一个-1 的时候，判断 下一个也是-1，那这组数据就pass了。
          b，c 去重
            去重逻辑应当放在已经收集了一组三元组之后
            b: nums[left] 和 nums[left+1] 比，如果相等left向右移动
              for left < right && b == nums[left+1] { // b去重
left++
}
            c: nums[right] 和 nums[right+1] 比，如果相等right向左移动
              for left < right && c == nums[right-1] { // c去重
right--
}
      GIF演示
  18. 四数之和
    思路
      在三数之和的基础上，多套一层for循环 k，但是不能判断 nums[k] > target 就返回了，因为这道题的 target 是任意值。
如果 target 是负数，这个和可能会越加越小的
      双指针法
        两层for循环 nums[k] + nums[i] 为确定值，循环内有 left 和 right 下标作为双指针。
寻找 nums[k] + nums[i] + nums[left] + nums[right] == target 的情况
  方法总结
    哈希法
      数组
        242.有效的字母异位词
        383.赎金信
        349.两个数组的交集
      map / set
        202.快乐数
        1.两数之和
        454.四数相加II
    双指针
      15.三数之和
      18. 四数之和