題目：

給定一個(gè)整數(shù)數(shù)組?nums?和一個(gè)整數(shù)目標(biāo)值?target，請(qǐng)你在該數(shù)組中找出 和為目標(biāo)值?target? 的那倆個(gè)整數(shù)，并返回它們的數(shù)組下標(biāo)。

你可以假設(shè)每種輸入只會(huì)對(duì)應(yīng)一個(gè)答案，并且你不能使用兩次相同的元素。

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

題解代碼：

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {// 創(chuàng)建一個(gè)哈希表，用于存儲(chǔ)數(shù)組中的元素及其對(duì)應(yīng)的索引unordered_map<int, int> sum_map;// 遍歷數(shù)組中的每一個(gè)元素for(int i = 0; i < nums.size(); i++) {// 計(jì)算目標(biāo)值與當(dāng)前元素的差值int complement = target - nums[i];// 在哈希表中查找是否存在這個(gè)差值auto it = sum_map.find(complement);// 如果找到了差值，說(shuō)明之前已經(jīng)遍歷過(guò)這個(gè)差值對(duì)應(yīng)的元素if(it != sum_map.end()) {// 返回差值的索引和當(dāng)前元素的索引return {it->second, i};}// 如果沒(méi)有找到差值，將當(dāng)前元素及其索引存入哈希表sum_map[nums[i]] = i;}// 如果沒(méi)有找到符合條件的兩個(gè)數(shù)，返回空數(shù)組return {};}
};

題解分析：

假設(shè)?nums = [2, 7, 11, 15]，target = 9。

• 第一次迭代：i = 0，nums[i] = 2，complement = 9 - 2 = 7。哈希表中沒(méi)有?7，將?2?存入哈希表。

• 第二次迭代：i = 1，nums[i] = 7，complement = 9 - 7 = 2。哈希表中有?2，返回?2?的索引?0?和當(dāng)前索引?1，即?[0, 1]。

時(shí)間復(fù)雜度

• 時(shí)間復(fù)雜度：O(n)，其中?n?是數(shù)組?nums?的長(zhǎng)度。我們只需要遍歷一次數(shù)組，每次查找哈希表的時(shí)間復(fù)雜度是 O(1)。

• 空間復(fù)雜度：O(n)，哈希表最多存儲(chǔ)?n?個(gè)元素。

這個(gè)算法通過(guò)使用哈希表來(lái)存儲(chǔ)已經(jīng)遍歷過(guò)的元素及其索引，從而在 O(1) 的時(shí)間內(nèi)查找是否存在符合條件的差值，大大提高了效率。

?