EasyLeetCode01，两数之和（two sum）
目前C++系列每天更新，LeetCode题解不定期更新，老梁估计大概一周一篇到两篇的速度吧。如果喜欢这类文章，还请大家多多支持。github
好了，废话不多说，我们来看题目。
题意
给定一个全是int的数组nums和一个整数target，要求返回两个下标，使得数组当中这两个下标对应的和等于target。
你可以假设一定值存在一个答案，并且一个元素不能使用两次。
其中：
2 <= nums.length <= 1e4-1e9 <= nums[i] <= 1e9-1e9 <= target <= 1e9
解法一：无脑枚举
在数据里面找到两个数等于target，很明显可以进行枚举。
不过要使用枚举也需要解决几个问题，首先，需要枚举的数量。在这题当中，我们需要枚举任意两个数的组合，对于长度为n的数组来说，我们知道这样的组合一共有Cn2=n(n−1)2C_n^2=\frac{n(n-1)}{2}Cn2=2n(n−1)种，数量级和n2n^2n2相当，所以近似可以看成是n2n^2n2种。
对于这道题来说，数组的最大长度是1e4，平方之后的量级是1e8，差不多是C++一秒能够执行的量级。勉勉强强可以接受大概率不会超时。
其次，是重复的情况。毕竟两两的组合这么多，如何保证得到的答案结果唯一呢？如果不唯一怎么办？
好在这道题当中替我们进行了保证，题意中明确说明了，答案唯一。既然如此，我们就可以大胆写出代码了：
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { int n = nums.size(); vector<int> ret; for (int i = 0; i < n; i ++) { for (int j = i + 1; j < n; j++) { if (nums[i] + nums[j] == target) { ret.push_back(i); ret.push_back(j); return ret; } } } return ret; } }; 复制代码解法二：使用map
解法一的代码提交之后通过时间大约在400毫秒左右，仅仅超过了6%的用户，显然还不够完美，存在大量的优化空间。
那么，我们怎么进行优化呢？
显然比较直观的就是，我们枚举了所有的可能，这太耗时了，有没有办法可以不用遍历所有的组合，但是又能保证一定可以找到答案的？
答案当然是肯定的，利用的原理也很简单，我们知道了target，需要在数组中寻找到a和b两个数，使得a+b=target。但其实我们没有必要遍历所有a和b的组合，因为确定了a，b也就确定了，它等于target-a。所以我们只需要枚举所有的a，然后判断target-a元素是否存在即可。
那么问题来了，我们怎么判断target-a是否存在，并且找到它的位置呢？
答案很简单，使用STL中的map。map可以记录一个<key, value>的pair，我们把数组当中的数当做key，它出现的位置当做value。这样我们只需要提前将数组当中所有的元素都插入map当中，就可以了。
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { int n = nums.size(); vector<int> ret; map<int, int> mp; // 先把数组中元素插入map for (int i = 0; i < n; i++) { mp[nums[i]] = i; } for (int i = 0; i < n; i++) { // 枚举a，通过map判断target - a是否存在 int num2 = target - nums[i]; if (mp.count(num2)) { ret.push_back(i); ret.push_back(mp[num2]); } } return ret; } }; 复制代码这个代码也很简单吧，但是先别急着高兴，如果你提交的话就会发现上面的代码会有样例无法通过。为什么会无法通过呢？因为我们疏忽了一种情况，一般我们会把这种隐藏的不容易想到的情况称作“Trick”，可以看做是出题人使用的诡计。
有时候就算想到了解法，但是没有发现隐藏的trick也无法通过题目。所以我们不仅要想出算法，还要确保算法在所有极端情况下都能运行。
在这题当中，这个trick是元素的唯一性。因为我们使用了map，map要求所有的key必须唯一。如果数组当中存在重复的元素，那么后面读到的数据会覆盖前面的。覆盖会产生什么问题呢？显然会导致答案出错。
那么问题来了，在这题当中nums中的数唯一吗？题目中并没有说，题目中只说了确保解只有一个，但并没有说每个元素唯一。所以虽然题目没有明说，但我们依然需要对这个问题进行分析。
假设我们找到了a+b=target的答案，这里的a和b可能有重复吗？很明显，当a和b不相等的时候，它们都不会有重复。因为如果数组当中有两个a，那么意味着我们至少能够找到两个a和b的组合。这与题目中说的解只有一个矛盾，所以可以肯定，当a和b不等的时候，它们都只会出现一次。
那么剩下的就是a和b相等的时候了，这也正是本题的trick所在。a和b可能会相等，但是由于map中强制key唯一，所以只能找到一个。怎么解决呢？其实很简单，我们只需要加一个判断条件就可以解决：
添加备注 class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { int n = nums.size(); vector<int> ret; map<int, int> mp; for (int i = 0; i < n; i++) { mp[nums[i]] = i; } for (int i = 0; i < n; i++) { int num2 = target - nums[i]; // 额外增加了mp[num2] != i的条件 if (mp.count(num2) && mp[num2] != i) { ret.push_back(i); ret.push_back(mp[num2]); break; } } return ret; } }; 复制代码这段代码和上面几乎完全一样，只不过底下for循环的if判断当中额外增加了mp[num2] != i的条件。这个条件确保我们找到了num2不是当前的nums[i]，因为当a和b相等的时候，我们想要通过map去寻找b的位置，结果由于map中发生了覆盖，所以又找回了a的位置，从而引发出错。我们加上这个判断就可以避免这种情况。
到这里还没有结束，这段代码仍然可以优化。既然map会发生覆盖，那么我们其实没有必要一开始的时候就一股脑把所有元素全部插入，我们可以一边插入元素一边进行判断。
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { int n = nums.size(); vector<int> ret; map<int, int> mp; for (int i = 0; i < n; i++) { int num2 = target - nums[i]; // 先寻找num2是否存在 if (mp.count(num2)) { ret.push_back(mp[num2]); ret.push_back(i); return ret; } mp[nums[i]] = i; } return ret; } }; 复制代码在这段代码当中，我们没有在一开始的时候将nums数组的元素全部放入map。而是随着for循环逐渐插入的，在for循环当中，我们先去寻找了num2在map当中是否存在，再去插入的nums[i]。我们也没有再去判断mp[nums2] != i了，因为这时候nums[i]的值还没有插入map，所以一定不会相等。
其实这利用了加法的交换律，a+b=target也可以得到b+a=target。a和b两个数在数组当中一定有一个先后顺序，假设a排在b前面。由于我们没有事先把所有元素插入map，所以这时候是找不到b的，也就是找不到答案的。但当我们遍历到b的时候，一定可以找到a。并且由于我们是先判断再插入当前的元素，即使a和b相等，也不会发生覆盖。
到这里，我们就算是把这题真正做完了，不仅做出来了，而且还优化到了极致。明明是一道挺简单的题目，也没用到什么高深的算法，但是当我们深入去研究，却有这么多东西可以说。某种程度上来说，这也是算法的魅力之一。很小的细节都值得仔细研究分析，都能分析出成果来。甚至很多题的解题思路就在这些细小的分析上。
好了，关于这题就聊到这里，感谢大家的阅读。
作者：程序员老梁
链接：https://juejin.cn/post/7025065623151443976