Day 6, Leetcode problem 1: Two Sum, C++

逃避虽可耻，但有用。
但这句话恐怕在我身上行不通。
每一次当我遇到问题时，我只有两种选择:

这两种选择我都有试过，面对处理它这项选择，往往结果好更甚于逃避，因为，逃了一次，还会再遇见N次... ...
当我从leetcode网站点选等级为easy的第一道程式后，我立刻浮现了以上选项，因为这题对我不简单容易，但有鉴于过去大量失败经历，我只能面对问题。
以下是Two of the sum 部分内文
Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.

我们从输入与输出範例可以晓得，输入有阵列(整数，一大串整数)和单整数(阵列里挑两个加总的合)，然后，我们必须找出是哪两个数加总的，并输出他们在阵列的第几位。

好吧!因为我很久没有打C++程式了，我一时之间只有脑袋空白。

然而，我却记得平行运算的课程中，老师有提到暴力解以及时间複杂度。
如果是暴力解，就是写出双回圈，将输入的阵列一一相加跟目标数值比对，就完成了。时间複杂度是O(n^2)

由于我想不出来更好的解法，所以我决定从网路捞出解答来分析:

class Solution {public:    vector<int> twoSum(vector<int>&/*指标变数*/ nums, int target) {        map<int, int> mymap;//map 使用的是红黑树演算法，简单来说，就是map自行安排顺序，使搜寻更快速        vector<int> ans;        for(int i=0; i < nums.size(); i++){            if(mymap.find(nums[i]) != mymap.end()){ // 在的话就表示找到了，可以将结果取得，                ans.push_back(mymap[nums[i]]);                ans.push_back(i);                return ans;            }            else{                mymap[target - nums[i]] = i;//每一次从map中确认当下target-num是否在map中，                                            //没找到的话，就将一组(num, index)放进map中，            }        }        return ans;          }};

恩........我想我有待加强。所以到底为甚么是target-num呢?如果从例子找问题 [2,7,11,15], target = 9
第一圈当i=0时，进入else, mymap[9-2=7]=0;也就是mymap[7]=0;
第二圈当i=1时，进入if, mymap.find(7)!=mymap.end();这是因为，find会寻找key，而我们在i=0时，存了key=7, 值=0的map，所以map里是有以key为7的值。
mymap[nums[i]] =0, i=1, ans={0, 1}
也就是说，由于答案是a+b的情况下，我们可以将sum-a后的值作为key存起来，第几迴圈i作为map值储存。
若nums有值与sum-a一样，也就是b，我们就将map的值与当下迴圈i存入ans vector。
如果不对，map会继续存新的key和值，直到找到答案。
最后，因为只有单迴圈就能找到解，所以时间複杂度O(n)
我有点消化不良，也许之后再複习.......