哈希表

  • 适用条件：给出一个元素，判断在集合里是否出现过
  • 哈希结构：
    • 数组
    • set集合
    • map映射
  • 最常用：unordered_set
  • 简单操作：
    • unorder_set cnt(a, a+6)：输入参数为第一个元素和最后一个元素之后的迭代器，因此有a，a+1，a+2，a+3，a+4，a+5共6个元素
    • s.insert()：插入
    • s.erase()：删除
    • s.size()：大小，元素个数
    • s.empty()：空
    • s.find()：查找，返回迭代器。没找到返回end
    • s.count()：统计元素出现次数
    • s.end()：end()并不是最后一个元素，最后一个元素是end()-1。因此返回的是最后一个元素之后的迭代器

1有效字母异位词

  • 思路：哈希表-数组
  • 伪代码：
    1
    2
    3
    4
    5
    6
    int record[26] = 0;
    for 遍历s字符串
      频次表++
    for 遍历t字符串
      频次表--
    检查record是否全为0

2两个数组的交集

  • 思路：哈希表-set
  • 伪代码：
    1
    2
    3
    4
    5
    将数组1初始化为set
    for 遍历数组2
      如果数组1能find到，也就是有共同的元素
      添加到结果set里
    return vector 结果