更好的閱讀體驗請點擊 兩數之和。

題目：兩數之和

? 給定一個整數數組 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 <= 10^4
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
只會存在一個有效答案

題目來源：力扣（LeetCode）

解題思路一：

? 題意很清楚，就是要從一個數組里找到唯一存在的一對數的和為target，并返回他們的下標，很容易就能想到暴力：兩層循環分別枚舉一遍數組，如果nums[i] + nums[j] == target，就找到了答案，然后將其放入vector中返回即可，時間復雜度O(n^2)，勉強能過。

AC代碼

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

解題思路二：

? 這題比較友好，n的數據范圍比較小，但如果n的范圍更大，顯然是過不了的，故我們需要想一想別的 方法。

? 這里有一種非常巧妙的方法：哈希表。

? 我們只需要枚舉一次數組，然后在每一次枚舉時，我們需要做：

1. 判斷target - nums[i]是否存在哈希表中
2. 將nums[i]插入哈希表中

? 然后就能找到答案了。

? 解釋：由于數據只有一組解，假設答案為[i, j]（i < j），則當我們循環到j時，nums[i]一定會存在哈希表中，且有nums[i] + nums[j] = target，故一定能找到解。

? 時間復雜度：只掃描一遍數組，且哈希表的插入和查詢操作的復雜度是O(1)，故總時間復雜度為O(n)

AC代碼

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> hash;vector<int> res;for (int i = 0; i < nums.size(); i ++){int another = target - nums[i];if (hash.count(another)){res.push_back(i), res.push_back(hash[another]);return res;}hash[nums[i]] = i;}return res;}
};