1.两数之和

https://leetcode.cn/problems/two-sum/
简要说明：
1.给定一个数组和一个数字
2.要求找到数组中某两个元素，使得他们相加等于所给数字（将所给数字拆为数组中的某两个个元素）
3.以数组形式返回两个下标 否则返回空指针

• 返回的下标没有顺序要求
• 假设有唯一解，即只能在数组中找到两个或者零个元素符合要求

初始思路：

• [暴力算法] 做匹配：循环嵌套，外层循环先对数组进行遍历[i]，内层循环也对数组进行遍历[j]（但跳过外层循环的元素），遍历时检查元素[i]和元素[j]相加是否为所给数字

  • 时间复杂度： O(n^2), 最好情况一次通过，最坏情况内外循环执行完毕但找不到匹配元素，比较语句执行了n^2次
  • 空间复杂度： O(1), 解法消耗的空间与给定输入没有关联
  点击查看代码

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

优化思路

• [优化算法] 做匹配：在暴力匹配过程中，查找是消耗时间的大户。如果利用哈希表查找会更加快速。

  相关资料

  https://www.cnblogs.com/Brakeintime/p/18425002

  • 时间复杂度： O(n), 最好情况一次通过，最坏情况数组遍历完毕找不到元素，比较语句执行n次
  • 空间复杂度： O(n), 解法消耗的空间与给定数组大小线性相关（因为我们建立了哈希表）
  点击查看代码

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