哈希表

本文最后更新于 2024年11月15日下午

一些有关哈希表的题目

一、哈希表

（1）两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

解法：

（1）暴力

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n=nums.size();
        for(int i=0;i<n;i++){           //前后比较
            for(int j=i+1;j<n;j++){
                if(nums[i]+nums[j]==target){
                    return {i,j};
                }
            }
        }
        return {};
};

（2）哈希查找

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int>ht;  //定义键值对哈希表
        for(int i=0;i<nums.size();i++){
            auto it=ht.find(target-nums[i]);
            //auto为自动变量，即unordered_map<int,int>::iterator迭代器
            if(it!=ht.end()){
                return {i,it->second};//键存放nums值，值存放索引，查找键，返回值
            }
            ht[nums[i]]=i;
        }
        return {};
};

哈希表的知识点

在 C++ 中，哈希表通常使用 unordered_map 或 unordered_set，这两种数据结构都属于 STL（标准模板库）。它们基于哈希表实现，提供高效的查找、插入、删除操作。

以下是 unordered_map 和 unordered_set 常用的函数和操作：

1. `unordered_map`（键值对哈希表）常用函数

unordered_map 存储的是键值对（key-value），其中键（key）是唯一的，值（value）可以重复。

以下是简洁版的哈希表（unordered_map）用法大全：

1. 创建和初始化

#include <unordered_map>

unordered_map<int, string> map1;  // 空哈希表
unordered_map<int, string> map2 = {{1, "one"}, {2, "two"}};  // 初始化

2. 插入元素

1
2
3

map1[3] = "three";        // 使用下标插入元素
map1.insert({4, "four"});  // 使用 insert 插入元素
map1.emplace(5, "five");   // 使用 emplace 插入元素

3. 访问元素

1
2
3

cout << map2[1];           // 访问元素，若不存在则插入默认值
cout << map2.at(1);        // 使用 at() 访问，若不存在抛出异常
cout << map2.find(2)->second; // 通过 find 查找，返回迭代器

4. 删除元素

1
2
3

map2.erase(2);             // 删除指定键的元素
map2.erase(map2.begin());  // 删除第一个元素
map2.clear();              // 清空所有元素

5. 大小和容量

1 2	`cout << map1.size(); // 返回元素个数 cout << map1.empty(); // 检查是否为空`

6. 遍历哈希表

1
2
3

for (const auto& pair : map2) {
    cout << pair.first << ": " << pair.second << endl;
}

7. 查找元素

if (map2.find(3) != map2.end()) {
    cout << "Found 3!";
} else {
    cout << "Not Found!";
}

8. 修改元素

1 2	`map2[1] = "uno"; // 修改已有元素的值 map2[6] = "six"; // 如果不存在，会自动插入`

9. 获取键的哈希值

1	`size_t hash_val = map1.hash_function()(3); // 获取键 3 的哈希值`

2.`unordered_set`（仅存储键的哈希表）常用函数

以下是简洁版的 unordered_set 用法大全：

1. 创建和初始化

#include <unordered_set>

unordered_set<int> set1;            // 空的 unordered_set
unordered_set<int> set2 = {1, 2, 3}; // 初始化 unordered_set

2. 插入元素

1 2	`set1.insert(4); // 插入元素 set1.emplace(5); // 使用 emplace 插入元素`

3. 访问元素

unordered_set 不支持通过下标访问元素，只能通过遍历或查找来访问元素。

1
2
3

for (const auto& num : set2) {
    cout << num << " ";  // 遍历访问元素
}

4. 删除元素

1
2
3

set1.erase(4);            // 删除指定元素
set1.erase(set1.begin()); // 删除第一个元素
set1.clear();             // 清空所有元素

5. 大小和容量

1 2	`cout << set1.size(); // 返回元素个数 cout << set1.empty(); // 检查是否为空`

6. 查找元素

if (set2.find(3) != set2.end()) {
    cout << "Found 3!";
} else {
    cout << "Not Found!";
}

7. 检查元素是否存在

unordered_set 会自动忽略重复元素。

1	`set2.insert(3); // 插入重复元素不会改变 set2`

8. 遍历元素

1
2
3

for (const auto& num : set2) {
    cout << num << " ";  // 遍历访问所有元素
}

3. 迭代器相关操作

begin() 和 end()
返回指向容器第一个元素的迭代器和指向容器末尾后一个位置的迭代器。

1
2
3

for (auto it = map.begin(); it != map.end(); ++it) {
    cout << it->first << ": " << it->second << endl;  // 打印每一个键值对
}

cbegin() 和 cend()
返回常量迭代器，不能修改容器中的元素。

1
2
3

for (auto it = map.cbegin(); it != map.cend(); ++it) {
    cout << it->first << ": " << it->second << endl;
}

（2）字母异位词分组

给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。

字母异位词是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]
示例 2:

输入: strs = [“”]
输出: [[“”]]
示例 3:

输入: strs = [“a”]
输出: [[“a”]]

思路

把字符串排序，排序结果作为哈希键，用vector把键相同的字符串放在一起作为哈希值。

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>>ans;
        //怎么设计排序来创造哈希键
        unordered_map<string,vector<string>>ht;
        /*for(int i=0;i<strs.size();i++){
            string str=strs[i];
            sort(strs[i].begin(),strs[i].end());
            ht[strs[i]].emplace_back(str);
        }*/
        for(string& str: strs){
            string s=str;
            sort(str.begin(),str.end());
            ht[str].emplace_back(s);
        }
        for(auto it=ht.begin();it!=ht.end();it++){
            ans.emplace_back(it->second);
        }
        return ans;

    }
};

vector向量用法

以下是简洁版的 std::vector 用法总结：

1. 创建和初始化

1
2
3

vector<int> vec1;              // 空的 vector
vector<int> vec2(5, 0);        // 5 个元素，初始化为 0
vector<int> vec3 = {1, 2, 3};  // 初始化列表

2. 访问元素

cout << vec3[2];          // 使用索引访问
cout << vec3.at(2);       // 使用 at() 访问（带边界检查）
cout << vec3.front();     // 第一个元素
cout << vec3.back();      // 最后一个元素

3. 修改元素

vec3[2] = 10;             // 通过索引修改
vec3.at(2) = 20;          // 使用 at() 修改
vec3.front() = 30;        // 修改第一个元素
vec3.back() = 40;         // 修改最后一个元素

4. 添加元素

1
2
3

vec3.push_back(6);        // 添加元素到末尾
vec3.emplace_back(7);     // 在末尾直接构造元素
vec3.insert(vec3.begin(), 15);  // 插入元素到指定位置

5. 删除元素

1
2
3

vec3.pop_back();          // 删除最后一个元素
vec3.erase(vec3.begin()); // 删除第一个元素
vec3.clear();             // 清空所有元素

6. 大小和容量

1
2
3

cout << vec3.size();      // 元素个数
cout << vec3.capacity();  // 容量
cout << vec3.empty();     // 是否为空

7. 遍历元素

1
2
3

for (int num : vec3) {    // 使用范围基于的 for 循环遍历
    cout << num << " ";
}

8. 排序

1	`sort(vec3.begin(), vec3.end()); // 升序排序`

9. 查找元素

auto it = find(vec3.begin(), vec3.end(), 10);  // 查找元素
if (it != vec3.end()) {
    cout << "Found";
}

10. 反转元素

1	`reverse(vec3.begin(), vec3.end()); // 反转元素顺序`

11. 交换两个 `vector`

1 2	`vector<int> vec4 = {4, 5, 6}; vec3.swap(vec4); // 交换 vec3 和 vec4 内容`

范围基于的 for 循环
C++ 中的 范围基于的 for 循环 用于简化遍历容器：

这是右对齐的文本

1.语法：
1
2
3
for (元素类型& 元素 : 容器) { // 操作元素 }
2.示例：
- 数组：for (int num : arr) { }
- **vector**：for (int& num : vec) { }
- **unordered_map**：for (const auto& pair : map) { }
3.const和引用

1. 非 `const` 引用（可以修改元素）：

如果你想修改容器中的元素，可以使用非 const 引用：

1
2
3

for (int& num : nums) {
    num *= 2;  // 将每个元素乘以 2
}

2. `const` 引用（只能读取元素）：

如果你不需要修改容器中的元素，使用 const 引用来避免不必要的拷贝：

1
2
3

for (const int& num : nums) {
    cout << num << " ";  // 只能读取元素，不能修改
}

const 引用确保了容器元素在遍历过程中不会被修改，并且避免了可能的拷贝开销。

4.适用范围：

范围基于的 for 循环适用于所有支持迭代器的容器，如：

std::vector
std::list
std::deque
std::set 和 std::map
std::array（C++11及以后）
原始数组

但是，它不适用于需要根据索引访问元素的情况，例如 std::string 或者一些自定义的容器。

（3）最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2：

输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

提示：

0 <= nums.length <= 105
-109 <= nums[i] <= 109

分析：不可以使用sort快排，时间复杂度为O（nlogn）。使用哈希表set，不会重复插入相同元素，无序,只有键无值。

解法一：会超时

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int>ht;
        for(const int& num : nums){
            ht.insert(num);
        }
        int ans=0;
        for(const int& num : ht){
            int currentnum=num;
            int currentans=1;
            while(ht.count(currentnum+1)){
                currentans++;
                currentnum++;
            }
            ans=max(ans,currentans);
        }
        return ans;
    }
};

解法二：完全正确

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int>ht;
        for(const int& num : nums){
            ht.insert(num);
        }
        int ans=0;
        for(const int& num : ht){//因为上面传入ht内的num是const，所以加const。
            int currentnum=num;
            int currentans=1;
            //!!!!重点，如果前一个数不存在，这个数才是起点，减少重复
            if(!ht.count(num-1)){
                while(ht.count(currentnum+1)){
                    currentans++;
                    currentnum++;
                }
            }
            ans=max(ans,currentans);
        }
        return ans;
    }
};

LeetCode

#C++ #LeetCode

哈希表

http://sue-channing.github.io/2024/11/12/哈希表/

作者

Sue-Channing

发布于

2024年11月12日

许可协议

金山笔试-测试工程师上一篇

我的文章下一篇

哈希表

一、哈希表

（1）两数之和

哈希表的知识点

1. unordered_map（键值对哈希表）常用函数

1. 创建和初始化

2. 插入元素

3. 访问元素

4. 删除元素

5. 大小和容量

6. 遍历哈希表

7. 查找元素

8. 修改元素

9. 获取键的哈希值

2.unordered_set（仅存储键的哈希表）常用函数

1. 创建和初始化

2. 插入元素

3. 访问元素

4. 删除元素

5. 大小和容量

6. 查找元素

7. 检查元素是否存在

8. 遍历元素

3. 迭代器相关操作

（2）字母异位词分组

vector向量用法

1. 创建和初始化

2. 访问元素

3. 修改元素

4. 添加元素

5. 删除元素

6. 大小和容量

7. 遍历元素

8. 排序

9. 查找元素

10. 反转元素

11. 交换两个 vector

范围基于的 for 循环

1.语法：

2.示例：

3.const和引用

1. 非 const 引用（可以修改元素）：

2. const 引用（只能读取元素）：

4.适用范围：

（3）最长连续序列

1. `unordered_map`（键值对哈希表）常用函数

2.`unordered_set`（仅存储键的哈希表）常用函数

11. 交换两个 `vector`

范围基于的 `for` 循环

1. 非 `const` 引用（可以修改元素）：

2. `const` 引用（只能读取元素）：