【LeetCode力扣热题100】【LeetCode 1】两数之和

方法一：暴力循环

两层循环，遍历所有的组合，直到满足条件，返回结果。

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

方法二：哈希表

循环遍历一次，用map存储遍历过的元素和索引，元素为map的key，索引为map的value。每次遍历时在map中查找等于【target - nums[i]】的key，找到则返回答案，未找到则将元素和索引存入map。

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

注：map和unordered_map的区别

std::map

• 内部实现：std::map通常是基于红黑树（一种自平衡二叉搜索树）实现的。这意味着元素会按照键排序，并且保证了所有操作（插入、删除、查找）的时间复杂度为O(log n)。
• 查找开销：由于它是一个有序的数据结构，所以查找一个元素需要进行树的遍历，平均时间复杂度为O(log n)。
• 插入/删除开销：同样地，插入或删除一个元素也需要O(log n)的时间，因为可能需要重新平衡树以保持其性质。
• 内存使用：通常比std::unordered_map占用更多内存，因为每个节点除了存储数据外还需要存储额外的指针用于维持树结构。
• 有序性：std::map中的元素是按键的顺序排列的，这对于需要有序访问的应用场景非常有用。

std::unordered_map

• 内部实现：std::unordered_map基于哈希表实现，元素之间没有固定的顺序。它通过哈希函数将键映射到桶中，从而提供平均情况下的常数时间复杂度O(1)的操作。
• 查找开销：在理想情况下（即没有哈希冲突），查找操作的时间复杂度为O(1)，但在最坏的情况下（例如当所有元素都映射到了同一个桶时），查找时间可能会退化到O(n)。
• 插入/删除开销：同样地，在没有哈希冲突的情况下，插入和删除的时间复杂度也是O(1)。然而，随着哈希冲突的增加，性能也会下降。
• 内存使用：一般而言，std::unordered_map相比std::map更节省空间，因为它不需要维护树结构所需的额外指针。
• 无序性：std::unordered_map中的元素不是按任何特定顺序排列的，因此如果你的应用程序依赖于按键排序，则不适合使用这个容器。