Leetcode100-两数之和

参见官方题解

一、学到的知识

1. 正面寻找两个数之和相加等于某个数，如 a+b = c，不如反过来寻找 a = c - b

   正面寻找需要两层 for 循环，把每个数都进行遍历，所以时间复杂度较高

   反过来则可以通过维护一个 a 的集合，每次通过查询 c - b 是否在集合中，判断是否存在 a = c - b

   存在，则返回答案；不存在，则将 a 插入集合中， 待下次查询

2. 想一下，我们为什么把 a 插入集合中，而不是 c - b呢？

   如果把 c - b 插入集合，意味着我们将判断 a 是否在集合中，总之就是要判断是否存在 a = c - b，两者写法其实都可以

二、代码

1. 版本1
   时间复杂度 O(N)
   空间复杂度 O(1)

   比较好想到的一个方法是先使用一层 for 循环枚举 a，再使用一层 for 循环枚举 b，判断 a + b == c 是否为真即可
   而且也容易想到一点优化，对于位于 x 位置的元素，1…x-1次循环的时候，nums[x]已经被匹配过，所以无需再匹配，所以在代码中，可以看到，第二层枚举 b 的循环，从 i + 1 开始

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

2. 版本2
   时间复杂度 O(NlogN)
   空间复杂度 O(N)

   这是版本1的优化， 前文提过，需要寻找 a + b = c，我们可以把 b 移至右侧，寻找 a = c - b，我们很自然的想到，可以维护一个数的集合，再从中寻找元素是否存在

   而这个集合的查找的复杂度，就决定了我们算法的复杂度，在代码中，我们使用了标准库中的 map，它的查找效率是 LogN

   class Solution
   {
   public:std::vector<int> twoSum(std::vector<int>& nums, int target){const int size = nums.size();map<int, int> Map;for (int i = 0; i < size; ++i){const int gap = target - nums[i];auto iterator = Map.find(gap);if (iterator != Map.end()){return {iterator->second, i};}Map.insert({nums[i], i});}return {-1, -1};}
   };