焦逸凡（JIAO Yifan）

LeetCode - 简单 - 1-两数之和（开个新坑）

Wiki LeetCode

写在前面

由于某些因素，决定从今天开始，每天刷两道算法题。题目来自LeetCode 热题 100，从简单的题做起。考虑到目前的生产环境使用Python语言，C++早已生疏，所以这个系列的题目在第一遍刷的时候，都会使用C++来实现。后续复习时，会用Python再做一遍。为了便于归档管理，所有LeetCode相关的内容都会写在Wiki中。

时间有限，有的题目可能只能写出一个比较简单的解法，或者直接参考LeetCode官方题解。

——2023年11月1日，于雁栖湖3公寓

两数之和

题目描述

想法

想法1

最自然的想法是暴力枚举，写两个循环遍历数组中的所有值，判断两个数之和是否等于目标值。这种方法的时间复杂度为$O(N^2)$，空间复杂度为$O(1)$。

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

        }
        return {};
    }
};

想法2

一般我能想到的方法都不是最佳方案，所以想法2来自题解，利用哈希表来降低时间复杂度。

具体想法是，建立一个哈希表（字典/键值对），并在哈希表中存放已经遍历过的x。在遍历时，首先查询哈希表中是否存在target - x，如果存在，则返回target - x的索引和当前索引。如果不存在，则将x存入哈希表中。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // 声明一个unordered_map，用于存放已经遍历过的x
        unordered_map<int, int> hashtable;
        // 遍历nums。由于是单循环，所以时间复杂度为O(N)
        for (int i = 0; i<nums.size(); ++i) {
            // 返回一个指向target - x的迭代器
            auto it = hashtable.find(target - nums[i]);
            // 如果找到了target - x，则返回target - x的索引和当前索引
            if (it != hashtable.end()) {
                return {it->second, i};
            }
            hashtable[nums[i]] = i;
        }
        return {};
    }
};

C++中unordered_map的用法

参考链接：https://c.biancheng.net/view/7231.html

这里复yu习xi一下C++中的unordered_map的用法。

unordered_map 容器，直译过来就是”无序 map 容器”的意思。所谓“无序”，指的是 unordered_map 容器不会像 map 容器那样对存储的数据进行排序。换句话说，unordered_map 容器和 map 容器仅有一点不同，即 map 容器中存储的数据是有序的，而 unordered_map 容器中是无序的。

unordered_map 容器在头文件中，并位于 std 命名空间中。因此，如果想使用该容器，代码中应包含如下语句：

#include <unordered_map>
using namespace std;

unordered_map 容器模板的定义如下所示：

template < class Key,                        //键值对中键的类型
           class T,                          //键值对中值的类型
           class Hash = hash<Key>,           //容器内部存储键值对所用的哈希函数
           class Pred = equal_to<Key>,       //判断各个键值对键相同的规则
           class Alloc = allocator< pair<const Key,T> >  // 指定分配器对象的类型
           > class unordered_map;

unordered_map容器的成员方法（常用）

成员功能
begin()返回指向容器中第一个键值对的正向迭代器。
end()返回指向容器中最后一个键值对之后位置的正向迭代器。
empty()若容器为空，则返回 true；否则 false。
size()返回当前容器中存有键值对的个数。
emplace()向容器中添加新键值对，效率比 insert() 方法高。
emplace_hint()向容器中添加新键值对，效率比 insert() 方法高。
insert()向容器中添加新键值对。
erase()删除指定键值对。
clear()清空容器，即删除容器中存储的所有键值对。
swap()交换 2 个 unordered_map 容器存储的键值对，前提是必须保证这 2 个容器的类型完全相等。
count()检查容器中是否存在与指定键匹配的键值对，若存在，则返回 1；否则返回 0。
find(key)查找以 key 为键的键值对，如果找到，则返回一个指向该键值对的正向迭代器；反之，则返回一个指向容器中最后一个键值对之后位置的迭代器（如果 end() 方法返回的迭代器）。

文档信息

Search

    Table of Contents