1. 两数之和 two sum

题目描述

given an array of integers, return indices of the two numbers such that they add up to a specific target.

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

you may assume that each input would have exactly one solution, and you may not use the same element twice.

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

自解_暴力法

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

• 与官方题解1类似，暴力法
• 时间复杂度：(o(n^2))，对于每个元素，试图通过遍历数组的其余部分来寻找它所对应的目标元素。
• 空间复杂度：(o(1))

注意

1. error: control reaches end of non-void function：控制到达非void函数的结尾。即本应带有返回值的函数到达结尾后可能并没有返回任何值

   本题中有可能找不到目标值，所以需要在循环检测外也返回一个值，否则会出现此错误

2. 想要返回vector时，如果是在调用函数内部创建的vector，会出问题。解决方法：将需要返回的vector引用值作为参数传进函数，在函数内部使用引用。而函数类型设置为bool

   参考：

参考官方题解_map

class solution { public:     vector<int> twosum(vector<int>& nums, int target) {         map<int, int> index;         vector<int> ans(2);         for (int i = 0; i < nums.size(); i++){             if (index.find(target - nums[i]) != index.end()){                 ans[0] = index.find(target - nums[i]) -> second;                 ans[1] = i;                 return ans;             }             else{                 index.insert(pair<int,int>(nums[i],i));             }         }         return ans;     } };

• 时间复杂度：(o(nlog(n)))，将元素与索引放入map，利用map进行查找。由于c++的map是基于红黑树实现的，查找的时间复杂度约为(log(n))，所以时间复杂度为 (o(nlog(n)))。

• 空间复杂度：(o(n))，所需的额外空间取决于map中存储的元素数量，该表中存储了 (n) 个元素，但c++的map基于红黑树实现，该树的一个节点在不保存数据时，占用16字节的空间，包括一个父节点指针，左右孩子指针，还有一个枚举值(标示红黑的，相当于平衡二叉树中的平衡因子)，可见，map还是很耗内存的。

  参考：c++ map详解

参考官方题解_unordered_map

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

• 时间复杂度：(o(n))，unordered_map查找复杂度(o(1))，最坏情况(o(n))
• 空间复杂度：(o(n))

注意

1. unordered_map
   • c++ 11标准中加入了unordered系列的容器。unordered_map记录元素的hash值，根据hash值判断元素是否相同。
   • map相当于java中的treemap，unordered_map相当于hashmap。

   • 无论从查找、插入上来说，unordered_map的效率都优于hash_map，更优于map；而空间复杂度方面，hash_map最低，unordered_map次之，map最大。

     参考：详细介绍c++stl：unordered_map

2. vector 初始化，可直接用{}包含元素，题目中需要返回的vector可以直接在返回时定义

   参考：