1 两数之和

其实C++才是最适合研究算法的语言，但是我已经很多年没有碰cpp了，上一次碰的时候应该还是大二打第二次蓝桥杯的时候用的，或许我都快把万能头怎么写给忘掉了。

#include<bits/stdc++.h>
using namespace std;
结果居然是用Python写的这道题。因为最近几乎只是用过这一种语言。
一开始犯了很愚蠢的错误，我没有看清变量名，反而把初始化的数据结构名当作变量名了。
算法题的函数传参似乎都比较严格。在函数声明的时候就已经规范好了数据类型。
写了一个很基础的n^2遍历。

这里有一个时间复杂度更低的方法O(1)就是哈希表 hash table。
unordered_map
值得一提的是，我看了人家hashtable的c++题解之后，立刻提出了一个问题：
“在不考虑内部顺序和哈希冲突的情况下，hash table的功能是否和dictionary数据类型有点相似呢？”

---

是的，在不考虑内部顺序和哈希冲突的情况下，哈希表(hash table)的功能确实与字典(dictionary)数据类型非常相似。
实际上，Python的字典(dict)就是使用哈希表作为其底层实现的。这两者之间的关系非常紧密：

键值对存储：两者都是通过键值对(key-value pairs)来存储数据。
快速查找：两者都提供接近O(1)的时间复杂度进行查找操作。也就是说，无论字典有多大，查找一个键所需的时间基本是常数时间。
通过键访问：两者都是通过键来访问对应的值，而不是通过索引位置。

不过，当我们考虑内部顺序和哈希冲突时，确实会发现一些区别：

内部顺序：传统的哈希表通常不保证顺序，而Python的字典从Python 3.7开始保证了插入顺序。
哈希冲突处理：不同哈希表实现可能使用不同的哈希冲突解决策略，例如开放寻址法或链式哈希。Python的字典使用开放寻址法来处理哈希冲突。

---

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

作者：御三五 🥇
链接：https://leetcode.cn/problems/two-sum/solutions/657225/tu-jie-guan-fang-tui-jian-ti-jie-liang-s-02xs/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

---

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashtable = dict()
        for i, num in enumerate(nums):
            if target - num in hashtable:
                return [hashtable[target - num], i]
            hashtable[nums[i]] = i
        return []

作者：御三五 🥇
链接：https://leetcode.cn/problems/two-sum/solutions/657225/tu-jie-guan-fang-tui-jian-ti-jie-liang-s-02xs/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

---

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        length = len(nums)
        for i in range(length):
            for j in range(i+1, length):
                if nums[i]+nums[j] == target:
                    result = [i,j]
                    return result

C++容器

对于.find() 方法对于所有 C++ 标准库中的 unordered_ 系列容器基本上都是一样的。这些容器包括：
-unordered_map
-unordered_multimap
-unordered_set
-unordered_multiset
所有这些容器的 .find() 都返回一个迭代器，如果找到了元素，返回指向该元素的迭代器，如果没找到元素，返回 容器.end()

时间复杂度：
平均情况：O(1)（常数时间）
最坏情况：O(n)（当哈希冲突严重时）

用法：

auto it = container.find(key);
if (it != container.end()) {
    // 找到了元素
}

这里auto是自动分配类型，因为这里是一个容器类型，通常就直接用auto自动适配了。
对于map而言，find()搜索的是key。

对于unordered_map<int,int> example访问key和value：
example->first 访问key
example->second 访问value
此外，如果要返回容器类型，那么是用{}来包裹值。

// 创建并初始化vector
vector<int> nums = {1, 2, 3, 4, 5};  // 初始化一个包含5个元素的vector

// 直接构造
vector<int> nums2 {1, 2, 3, 4, 5};   // 等同于上面的写法

// 函数返回
return {1, 2};                      // 如果函数返回类型是vector<int>，这会创建并返回包含两个元素的vector

C++11 引入了花括号初始化（uniform initialization）作为一种通用的初始化容器的方式
适用于所有标准容器类型（vector, map, set 等）