两数之和(每天刷力扣hot100系列)

目录

题目介绍：

解法1：暴力枚举

解法2：哈希表（散列表）

​​​​​​​
题目介绍：

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

时间复杂度：O(N2)

空间复杂度：O(1)

这个就是穷举，没什么好解释的

解法2：哈希表（散列表）

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)

空间复杂度：O(N)

哈希表的原理就是空间换时间，提前创建固有的一定空间，如果空间无限大可以就直接定位到值所在的键，存放索引。由于空间有限，则可以通过取余存放到固定的位置，如果遇到哈希冲突，则顺延，查找的时候也是直接找想要找的值的索引处，取出数组的索引值。哈希桶则类似于链表，哈希冲突的时候就连在原先的索引值后面。（负载因子为存放的数据占总空间的大小，涉及到扩容）。

在这里就是创建一个基于哈希表的键值对容器unordered_map，然后遍历一遍数组，遍历规则是找对应x数的target-x的数值，在创建的哈希表里面找，如果找到了，则返回对应键的数组索引值，找不到则将其索引值根据数值存入对应键处，好拿好取。如果没有则返回空。