C++描述 LeetCode 1. 兩數之和哈希表實作

??大家好，我叫亓官劼（qí guān jié ），在CSDN中記錄學習的點滴歷程，時光荏苒，未來可期，加油~博主目前僅在CSDN中寫博客，唯一博客更新的地址為：亓官劼的博客，同時正在嘗試在B站中做一些內容分享，B站主頁為：亓官劼的B站主頁

本文原創為亓官劼，請大家支持原創，部分平臺一直在惡意盜取博主的文章！！！
若需聯系博主，可以聯系本人微信：qiguanjie2015

題目

給定一個整數陣列 nums 和一個整數目標值 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 <= 103
-109 <= nums[i] <= 109
-109 <= target <= 109
只會存在一個有效答案

解題思路

這題是一個簡單題，LeetCode的第一題，我們可以直接使用暴力的雙重回圈來解這題，時間復雜度是 O ( n 2 ) O(n^2) O(n2)，我們也可以先排序在查找，但是排序的時間就是 O ( n l o g n ) O(nlogn) O(nlogn) 了，這里我們采用了哈希表的實作方法，可以將時間復雜度壓縮到 O ( n ) O(n) O(n) ，我們從頭開始遍歷，每到一個值判斷是否有值為target - nums[i]的，如果有則直接回傳，如果沒有則將當前值加入哈希表，以便后面的查找，

在哈希表選取時，這里選擇了unordered_map,之所以選擇unordered_map而不是map的原因是：unordered_map內部實作了哈希表，雖然建立程序相對慢一點，但是查詢快，map內部實作了紅黑樹，建立相對快一點，但是查詢慢，這題中我們將會大量使用查詢，所以我們選則了unordered_map，

演算法實作

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // 這里使用unordered_map而不用map的原因：unordered_map內部實作了哈希表，建立耗時較多，但是查找時間非常短，這題我們需要頻繁查找，所以使用unordered_map
        unordered_map<int, int> mp;
        for (int i = 0; i < nums.size(); ++i) {
            // 每次查找是否有值為target - nums[i]，如果有，則直接回傳，如果沒有，則將這個值加入哈希表，方便后面查找
            auto it = mp.find(target - nums[i]);
            if (it != mp.end()) {
                return {it->second, i};
            }
            mp[nums[i]] = i;
        }
        // 如果查找不到，則回傳空
        return {};
    }
};