Leetcode刷题笔记--哈希表

系列文章目录

���示：写完文章后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

• 系列文章目录
• 前言
• 一、哈希表基础知识
• • 1.1 unordered_map
  • 1.2 unordered_set
  • 二、相关习题
  • • 2.1 字母异位数相关习题
    • 2.2 unordered_set相关题目
    • 2.3 unordered_map相关题目
    • 总结

      ---

      前言

      提示：这里可以添加本文要记录的大概内容：

      一、哈希表基础知识

      在力扣习题当中，哈希表是非常常见的知识点。 哈希表通过哈希函数将键映射到索引位置，因此在理想情况下，查找和插入操作的时间复杂度为O(1)。这使得哈希表非常适合于需要快速检索的场景。 因此，在某些场景中有重要的作用。本文中主要介绍哈希表的两种常见形式：unordered_map和unordered_set,这也是做题中最常用的两种类型。

      （）

      1.1 unordered_map

      unordered_map是一个将key和value关联起来的容器，它可以高效的根据单个key值查找对应的value。key应该是唯一的，key和value的数据类型可以不相同。

      与 map 不同，unordered_map 不保证元素的顺序，而是通过哈希函数将键映射到桶（buckets），因此插入、删除和查找操作的平均时间复杂度都是常数时间 O(1)。适用于检索单个元素，效率很高。

      下面是unordered_map的C++基本用法。其中，最重要的是find函数。他用于查找key所在的元素。如果找到则返回指向对应键值对的迭代器，否则返回 end() 迭代器，表示未找到该键。

      //STL中map的基本用法#include void basic(){std::unordered_map myMap;// 添加键值对myMap["Alice"] = 25;myMap["Bob"] = 30;myMap["Charlie"] = 35;//删除键值对myMap.erase("Bob");// 检查键是否存在if (myMap.find("David") != myMap.end()) {std::cout std::cout     std::cout std::cout     std::unordered_map        if (std::isalpha(c)) { // 只统计字母            charCount[c]++;        }    }    // 输出结果    for (const auto& pair : charCount) {        std::cout unordered_setstd::cout std::cout std::cout std::cout std::cout std::cout std::cout     std::unordered_set        if (numSet.count(num)  0) {            return true; // 已存在重复元素        }        numSet.insert(num);    }    return false; // 未找到重复元素}unordered_setif (set.count(num)  0) {ans.push_back(num);set.erase(num);}}return ans;}unordered_maphashset[num]++;}for (auto num : nums2) {if (hashset[num]  0) {ans.push_back(num);hashset[num]--;}}return ans;}unordered_mapif (map[a]  0) map[a]--;else return false;}/*for (auto it = map.begin();it!=map.end();it++){if (it-second  0) return false;}*/return true;    }        int record[26] = {0};        for (int i = 0; i