问题描述：
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例：
给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]
代码：
/* 暴力破解法 算法描述：从数组第一个元素开始，对于第一个元素，从第二个元素开始遍历数组看看是否它俩之 和为target；对于第二个元素，从第三个元素开始遍历看看是否它两之和为target，按此规律直到 找到两数之和为target，并返回它们的下标。如果两层循环都完成了，仍没有找到，则返回{}，表 示NULL。 算法分析：时间复杂度为 O(N^2) 空间复杂度为 O(1) */ class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { int n = nums.size(); for (int i = 0; i < n; i++){ /*从i+1开始。因为题中“数组中同一个元素不能使用两遍”，所以j不等于i，并且每一个位 于i之前的元素都已经和i匹配过，所以j也不能小于i。*/ for (int j = i + 1; j < n; j++){ if (nums[i] + nums[j] == target) return { i,j }; } } return {}; } }; //已知哈希表查找元素是很快的，其时间复杂度为O(1)，所以能否借助哈希表来降低时间复杂度呢？ /* 哈希表法 算法描述：创建一个哈希表，对于每一个nums[i]，首先查找哈希表是否存在target-nums[i]， 如果存在，则返回哈希表中该元素对应的索引以及当前i的值。如果不存在，则将nums[i]插入 到哈希表中。 算法分析：时间复杂度为 O(N) 空间复杂度为 O(N) 主要为哈希表的开销 */ class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { //创建一个unordered_map对象 unordered_map<int, int> hashtable; for (int i = 0; i < nums.size(); i++){ //查找hashtable中有无target - nums[i] auto it = hashtable.find(target - nums[i]); //如果存在 if (it != hashtable.end()) //it->second,即target-num[i]在数组中对应的下标 return { it->second,i }; //不存在，则将当前nums[i]和i添加入hashtable //it->second指的就是这里添加的某个i hashtable[nums[i]] = i; } return {}; } };心得：
暴力破解法使用了两层循环，每层循环的规模是N，所以时间复杂度是O(N^2)，但是空间复杂度是O(1)，因为临时变量所占空间并不是随着数组规模N的增加而增加。鉴于哈希表的查找能力强的优点，其查找时间复杂度为O(1)，所以一层循环加查找操作，其时间复杂度为O(N)，但是需要开辟一个空间给哈希表使用，所以空间复杂度为O(N)。第一次接触哈希表，对它的使用和原理还不了解，所以打算多做一些关于哈希表的练习题来熟悉哈希表的使用，然后再去学习什么是哈希表，进而学习哈希表的原理。