Leetcode---1.两数之和 （详解加哈希表解释和使用）

题目 两数之和

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

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

方法一：暴力枚举

思路及算法

最容易想到的方法是枚举数组中的每一个数 x，寻找数组中是否存在 target - x。

当我们使用遍历整个数组的方式寻找 target - x 时，需要注意到每一个位于 x 之前的元素都已经和 x 匹配过，因此不需要再进行匹配。而每一个元素不能被使用两次，所以我们只需要在 x 后面的元素中寻找 target - x。

代码

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 {};
    }
};

复杂度分析

时间复杂度：O(N²)，其中 N 是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次。

空间复杂度：O(1).

方法二：哈希表

思路及算法

注意到方法一的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此，我们需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，我们需要找出它的索引。

使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 O(N) 降低到 O(1)。

这样我们创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。

代码

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hashtable;
        for (int i = 0; i < nums.size(); ++i) {
            auto it = hashtable.find(target - nums[i]);
            if (it != hashtable.end()) {
                return {it->second, i};
            }
            hashtable[nums[i]] = i;
        }
        return {};
    }
};

复杂度分析

时间复杂度：O(N)，其中 N 是数组中的元素数量。对于每一个元素 x，我们可以 O(1) 地寻找 target - x。

空间复杂度：O(N)，其中 N 是数组中的元素数量。主要为哈希表的开销。

哈希表

哈希表的基本概念

哈希函数（Hash Function）：

1. 哈希函数将输入的键转换为哈希码，这个哈希码通常是一个整数。
2. 哈希码用于确定键值对在哈希表中的存储位置。
3. 一个好的哈希函数应当均匀地分布键，减少冲突的发生。

冲突（Collision）：

1. 当两个不同的键被哈希函数映射到同一个存储位置时，称为冲突。
2. 处理冲突的方法主要有两种：链地址法（Chaining）和开放地址法（Open Addressing）。

链地址法（Chaining）：

1. 每个存储桶存储一个链表或其他数据结构来处理冲突。
2. 当冲突发生时，新键值对被插入到对应存储桶的链表中。

开放地址法（Open Addressing）：

1. 当冲突发生时，寻找另一个空的存储桶来存储冲突的键值对。
2. 常见的开放地址法包括线性探测（Linear Probing）、二次探测（Quadratic Probing）和双重散列（Double Hashing）。

哈希表的操作

插入（Insert）：

1. 计算键的哈希码，找到对应的存储桶。
2. 如果没有冲突，直接插入。
3. 如果有冲突，根据冲突解决策略进行处理（例如链地址法或开放地址法）。

查找（Search）：

1. 计算键的哈希码，找到对应的存储桶。
2. 在存储桶中查找键值对。
3. 如果使用链地址法，可能需要遍历链表。

删除（Delete）：

1. 计算键的哈希码，找到对应的存储桶。
2. 在存储桶中查找并删除键值对。
3. 如果使用链地址法，可能需要遍历链表。

哈希表的优点和缺点

优点：

1. 快速查找、插入和删除： 平均情况下，这些操作的时间复杂度都是 O(1)。
2. 实现简单： 相对于平衡树等复杂数据结构，哈希表的实现较为简单。

缺点：

1. 需要处理冲突： 尽管冲突不可避免，但冲突处理机制（如链地址法或开放地址法）会影响性能。
2. 内存消耗： 哈希表通常需要额外的内存来存储链表或解决冲突，这在存储空间有限的情况下可能是个问题。
3. 无法有序遍历： 哈希表中的元素没有特定顺序，因此不能按顺序遍历所有键值对。

基本用法

在C++中，unordered_map 是标准库（STL）中的一种关联容器，提供了键值对的哈希表实现。下面是一些常见的操作：

1. 引入头文件

#include <unordered_map>

• 在使用 unordered_map 之前，需要引入 <unordered_map> 头文件。

2. 声明一个哈希表

std::unordered_map<int, int> hashtable;

• 声明一个键为 int，值也为 int 的哈希表。

3. 插入元素

hashtable[1] = 100;
hashtable.insert({2, 200});

• 使用 [] 操作符或 insert 方法插入键值对。

4. 访问元素

int value = hashtable[1];
auto it = hashtable.find(2);
if (it != hashtable.end()) {
    std::cout << "Found: " << it->second << std::endl;
}

• 使用 [] 操作符访问元素或使用 find 方法查找元素。

5. 删除元素

hashtable.erase(1);

• 使用 erase 方法删除键值对。

6. 遍历哈希表

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

使用范围 for 循环遍历哈希表中的所有键值对。

示例代码

下面是一些具体示例，展示如何使用 unordered_map：

示例 1：计数字符出现次数

#include <unordered_map>
#include <iostream>
#include <string>

int main() {
    std::string str = "hello world";
    std::unordered_map<char, int> char_count;

    // 统计每个字符出现的次数
    for (char c : str) {
        if (c != ' ') {
            char_count[c]++;
        }
    }

    // 输出字符出现的次数
    for (const auto& pair : char_count) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

示例 2：两数之和问题

#include <unordered_map>
#include <vector>
#include <iostream>

std::vector<int> twoSum(const std::vector<int>& nums, int target) {
    std::unordered_map<int, int> hashtable;
    for (int i = 0; i < nums.size(); ++i) {
        int complement = target - nums[i];
        auto it = hashtable.find(complement);
        if (it != hashtable.end()) {
            return {it->second, i};
        }
        hashtable[nums[i]] = i;
    }
    return {};
}

int main() {
    std::vector<int> nums = {2, 7, 11, 15};
    int target = 9;
    std::vector<int> result = twoSum(nums, target);
    if (!result.empty()) {
        std::cout << "Indices: " << result[0] << ", " << result[1] << std::endl;
    } else {
        std::cout << "No solution found." << std::endl;
    }
    return 0;
}

注意事项

性能

1. unordered_map 提供平均 O(1) 的插入、查找和删除操作，但在最坏情况下，这些操作可能是 O(n) 的。
2. 哈希表的性能高度依赖于哈希函数的质量和负载因子（元素数量与桶的数量之比）。

哈希函数

1. 自定义类型作为键时，需要提供自定义的哈希函数和相等函数。

内存开销

1. unordered_map 在存储键值对时会使用额外的内存来维护哈希桶。