廢話不多說，讓我們一起來看看題目吧。

Given an array of integers, return indices of the two numbers such that they add up to a specific target. 

You may assume that each input would have exactly one solution, and you may not use the same element twice.

https:///problems/two-sum/

翻譯

給定一個(gè)全是int的數(shù)組和一個(gè)整數(shù)target，要求返回兩個(gè)下標(biāo)，使得數(shù)組當(dāng)中這兩個(gè)下標(biāo)對(duì)應(yīng)的和等于target。

你可以假設(shè)一定值存在一個(gè)答案，并且一個(gè)元素不能使用兩次。

解答

找兩個(gè)數(shù)和等于target，第一反應(yīng)就是暴力枚舉。假設(shè)數(shù)組長(zhǎng)度是n，那么一個(gè)

雙重循環(huán)就可以搞定。用Python的話，分分鐘就可以寫出代碼。

for i in range(len(array)):    for j in range(len(array)):        if array[i] + array[j] == target:            return [i, j]

這樣做當(dāng)然是正確的，但顯然不是最好的答案。根據(jù)經(jīng)驗(yàn)，一般情況下O(n2)的算法都不是最優(yōu)解。

  引入map  

我們繼續(xù)寫出偽代碼：

for i in range(len(array)):    map[array[i]] = i;    if target - array[i] in map:        return [i, map[target - array[i]]]

這個(gè)算法看起來沒什么問題，但是如果你這么寫出代碼來提交一定過不了。

因?yàn)橛幸环N隱藏的情況沒有考慮到，一般我們會(huì)把這種隱藏的不容易想到的情況稱作“Trick”，可以看做是出題人使用的詭計(jì)。

題目當(dāng)中說了，同一個(gè)元素不能使用兩次，但是并沒有說數(shù)組當(dāng)中沒有重復(fù)的元素。map的使用有一個(gè)限制，就是不能有key值相同的元素。如果數(shù)組當(dāng)中存在重復(fù)的元素，那么后面讀到的數(shù)據(jù)會(huì)覆蓋前面的。覆蓋會(huì)產(chǎn)生什么問題呢？會(huì)導(dǎo)致我們沒有辦法判斷元素出現(xiàn)的次數(shù)。

舉個(gè)例子，比如：target=6， array=[3, 3]

由于我們使用了map，我們?cè)谟涗浵碌诙€(gè)3的時(shí)候，就會(huì)損失第一個(gè)3的信息。這樣我們就會(huì)錯(cuò)過答案，不過這個(gè)問題也并不是不能解決，我們可以用一個(gè)標(biāo)記記錄一下，是否有重復(fù)的數(shù)字或者是重復(fù)的數(shù)字是什么。不過這并不是完美的解決方案，我們沒有想到完美解法，是因?yàn)橛幸粋€(gè)潛在的條件被我們忽略了。

這個(gè)條件就是加法的交換律，也就是說a+b=target，那么b+a也應(yīng)該等于target。這當(dāng)然是一個(gè)廢話，但如果a和b之間存在順序的話就不一樣了。如果a的順序在b前面，那么我們應(yīng)該通過a去找b呢，還是應(yīng)該通過b去找a？

當(dāng)然是通過b去找a，因?yàn)閍在b之前，我們可以利用之前已經(jīng)遍歷過的信息查找。如果通過a去找b，那么我們需要再開辟一個(gè)循環(huán)遍歷。

想明白了這點(diǎn)，剩下的就簡(jiǎn)單了。

假設(shè)數(shù)組array一共有n個(gè)元素，分別是a0,a1,?,an?1。我們用一個(gè)map存儲(chǔ)之前出現(xiàn)過的元素的下標(biāo)，當(dāng)我們遍歷到i的時(shí)候，我們只需要判斷target?ai在不在map當(dāng)中即可。

因?yàn)榧僭O(shè)存在ai+aj=target,i<j。當(dāng)我們指針遍歷到i的時(shí)候找不出答案，因?yàn)?span role="textbox" aria-readonly="true" style="display: inline;line-height: normal;word-spacing: normal;overflow-wrap: normal;float: none;direction: ltr;max-width: none;max-height: none;min-width: 0px;min-height: 0px;border-width: 0px;border-style: initial;border-color: initial;">aj的值還沒有出現(xiàn)在map中。但是當(dāng)我們遍歷到j(luò)的時(shí)候，一定可以找到答案，因?yàn)?span role="textbox" aria-readonly="true" style="display: inline;line-height: normal;word-spacing: normal;overflow-wrap: normal;float: none;direction: ltr;max-width: none;max-height: none;min-width: 0px;min-height: 0px;border-width: 0px;border-style: initial;border-color: initial;">ai已經(jīng)出現(xiàn)過了。

通過利用加法交換律以及元素出現(xiàn)的先后順序，再結(jié)合map，我們只需要一次遍歷就可以找到答案。就算出現(xiàn)重復(fù)元素，也沒有關(guān)系，因?yàn)槲覀兪窍扰袛啻娌淮嬖?，再更新map。

最后，附上偽代碼：

for i in array.length:    if target - array[i] in map:        return i, map[target - array[i]]    else:        map.put(array[i], i)

這題本身并不難解，用到的知識(shí)也平淡無奇，不過要想能琢磨出其中的trick，并想到解法，并不容易，需要基于充分的思考和理解。

簡(jiǎn)單題也能有所收獲，祝大家刷題愉快。