1. 兩數之和

給定一個整數數組 nums 和一個整數目標值 target，請你在該數組中找出 和為目標值 target 的那 兩個 整數，並返回它們的數組下標。

你可以假設每種輸入只會對應一個答案。但是，數組中同一個元素在答案裏不能重複出現。

你可以按任意順序返回答案。

示例 1：

輸入：nums = [2,7,11,15], target = 9
輸出：[0,1]
解釋：因為 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：

輸入：nums = [3,2,4], target = 6
輸出：[1,2]
示例 3：

輸入：nums = [3,3], target = 6
輸出：[0,1]

提示：

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只會存在一個有效答案
進階：你可以想出一個時間複雜度小於 O(n2) 的算法嗎？

1. 遍曆求解

根據題意，對於給定一個數x，判斷是否存在target-x，比較容易想到的辦法是遍曆整個數組，並且因為不能重複出現元素，所以只需要判斷x之後的數是否滿足要求即可。代碼如下：

class Solution {
    
public:
//知識點1：vector的概念與性質
    vector<int> twoSum(vector<int>& nums, int target) {
    
        int n = nums.size();
//知識點2：i++和++i的區別
        for(int i = 0;i < n;++i)
        {
    
//對於每個數，它都與前面的數進行過匹配，因此從它之後的數開始匹配
            for(int j = i + 1;j < n;++j)
            {
    
               if(nums[i] + nums[j] == target)
               return {
    i,j};
        }
        return {
    };
    }
};

知識點1：vector的概念與性質

vector是順序容器，本質是動態數組。創建vector容器時需要說明該容器內元素的類型。如下：

vector<int> twoSum;

vector容器在做形參傳遞時，可以采用以下三種方式：

void init_vector1(vector<int>vectest);
void init_vector2(vector<int>&vectest);
void init_vector3(vector<int>*vectest);

init_vector1中是值傳遞，形參的改變不會對實參有影響，並且會調用vector的拷貝構造函數將實參的值複制給形參。

init_vector2和init_vector3分別是引用傳遞和指針傳遞，它們會對實參做出影響。

建議在實際應用中采用引用傳遞，如下文所示。

vector<int> twoSum(vector<int>& nums, int target);

知識點2：i++和++i的區別

1、賦值順序不同

i++先賦值後運算，++i先運算後賦值。

2、效率不同

++i的效率比i++高。因為i++先賦值後運算，因此要多生成一個局部對象。如下所示。

CDemo CDemo::operator++ ()
{
      //前置++
    ++n;
    return *this;
}
CDemo CDemo::operator ++(int k)
{
      //後置++
    CDemo tmp(*this);  //記錄修改前的對象
    n++;
    return tmp;  //返回修改前的對象
}

3、i++無法做左值，++i可以

左值是對應內存中有確定存儲地址的對象的錶達式的值，而右值是所有不是左值的錶達式的值。一般來說，左值是可以放到賦值符號左邊的變量。

但能否被賦值不是區分左值與右值的依據。比如，C++的const左值是不可賦值的；而作為臨時對象的右值可能允許被賦值。左值與右值的根本區別在於是否允許取地址&運算符獲得對應的內存地址。

2. 哈希錶

可以看出，遍曆求解中時間複雜度較高，可以從這一方面優化，也就是簡化查值過程。因此，可以采用建立哈希錶的方式，對於單個未知數x，利用哈希錶尋找target-x的時間複雜度可以降為O(1)，對於含有N個數的數組，整個算法的時間複雜度為O(N)；由於存儲哈希錶，空間複雜度為O(N)。代碼如下：

class Solution {
    
public:
    vector<int> twoSum(vector<int>& nums, int target) {
    
//知識點3：哈希錶
//建立哈希錶
        unordered_map<int,int>hashtable;
        for(int i = 0;i < nums.size();++i)
        {
    
//知識點4：auto標識符
//知識點5：迭代器iterator的概念與性質
//針對該數nums[i]，在哈希錶內查值。數組下標i為值，nums[i]數本身為鍵值。
           auto it = hashtable.find(target - nums[i]);
//若在已有哈希錶內查到值則返回對應下標。因為是與該數前面的數進行匹配，因此該數下標i返回時在後面。
           if(it != hashtable.end())
           return {
    it->second,i};
//將該數nums[i]加入哈希錶
           hashtable[nums[i]] = i;
         }
         return {
    };
    }
};

知識點3：哈希錶

哈希錶是一個采用鍵值和值相互對應的函數，在c++中，與哈希錶對應的容器是unordered_map（無序容器）。因此采用unordered_map建立哈希錶。

該句建立一個名為hashtable的，鍵值對為<int,int>類型的unordered_map容器。其中<int,int>是指鍵值對類型，前者是鍵的類型，後者是值的類型。

unordered_map<int,int>hashtable;

find(key)是unordered_map容器中尋找鍵key對應的值的成員方法。若鍵key與其值的鍵值對在容器中存在，則返回一個指向該鍵值對的正向迭代器，反之則返回一個指向容器中最後一個鍵值對之後比特置的迭代器。

auto it = hashtable.find(target - nums[i]);

該句判斷是否存在我們需要的鍵值對。成員方法end()生成指向容器中最後一個鍵值對之後比特置的迭代器。

if(it != hashtable.end())

知識點4：auto標識符

1、auto就是根據變量值推斷變量類型。
2、使用auto時必須初始化變量。
3、auto是一個占比特符，並不是一個類型，因此無法進行類型轉換之類的操作

知識點5：迭代器iterator的概念與性質

訪問、讀寫容器中的元素，需要使用迭代器iterator。容器可以看作為吉他，迭代器可以看作為撥片，吉他（容器）是聲音（元素）的載體，但是使吉他發出聲音（能够訪問到容器的元素）需要使用撥片（迭代器）。

迭代器根據訪問方式分為正向迭代器、雙向迭代器、隨機訪問迭代器。不同的訪問方式使得迭代器可以做的運算不同。

迭代器常用功能：
1、定義一個正向迭代器
容器類名::iterator 迭代器名;

vector<int>::iterator i; 

2、取得迭代器所指元素

a = *i;

3、移動迭代器，訪問下一個元素（移動方法視迭代器類別變化）

++i;

在unordered_map容器中，迭代器指向鍵值對，即指向兩個元素，鍵和值。因此通過迭代器訪問unordered_map容器時，需要說明訪問的是哪個元素。其中first是鍵，second是值。

return {
    it->second,i};

上句即為訪問鍵值對中的值。

參考文獻：

1. Vector容器
2. c++中vector做形參傳遞的問題
3. i++與++i的區別
4. unordered_map容器
5. auto標識符
6. 迭代器
7. Leetcode DAY2 兩數之和