給定一個(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è)答案。但是，數(shù)組中同一個(gè)元素在答案里不能重復(fù)出現(xiàn)。

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

示例

• 輸入：nums = [2,7,11,15], target = 9

• 輸出：[0,1]

• 解釋：因?yàn)?nums[0] + nums[1] == 9 ，返回 [0, 1] 。

暴力枚舉

我們最容易想到的方法是遍歷數(shù)組中的每一個(gè)數(shù) x，判斷數(shù)組中是否存在 target - x。

當(dāng)我們使用遍歷整個(gè)數(shù)組的方式尋找 target - x 時(shí)，需要注意到每一個(gè)位于 x 之前的元素都已經(jīng)和 x 匹配過(guò)，因此不需要再進(jìn)行匹配。而每一個(gè)元素不能被使用兩次，所以我們只需要在 x 后面的元素中尋找 target - x。

代碼如下：

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(N^2)，其中 N 是數(shù)組中的元素?cái)?shù)量。最壞情況下數(shù)組中任意兩個(gè)數(shù)都要被匹配一次。

• 空間復(fù)雜度：O(1)。

方法二：哈希表

注意到方法一的時(shí)間復(fù)雜度較高的原因是尋找 target - x 的時(shí)間復(fù)雜度過(guò)高。因此，我們需要一種更優(yōu)秀的方法，能夠快速尋找數(shù)組中是否存在目標(biāo)元素。如果存在，我們需要找出它的索引。

使用哈希表，可以將尋找 target - x 的時(shí)間復(fù)雜度降低到從 O(N) 降低到 O(1)。

這樣我們創(chuàng)建一個(gè)哈希表，對(duì)于每一個(gè) x，我們首先查詢哈希表中是否存在 target - x，然后將 x 插入到哈希表中，即可保證不會(huì)讓 x 和自己匹配。

代碼如下：

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(N)，其中 N 是數(shù)組中的元素?cái)?shù)量。對(duì)于每一個(gè)元素 x，我們可以 O(1) 地尋找 target - x。

• 空間復(fù)雜度：O(N)，其中 N 是數(shù)組中的元素?cái)?shù)量。主要為哈希表的開銷。

寫在最后

本文內(nèi)容出處是力扣官網(wǎng)，希望和大家一起刷算法，在后面的路上不變禿但是變強(qiáng)！

好兄弟可以點(diǎn)贊并關(guān)注我的公眾號(hào)“javaAnswer”，全部都是干貨。