本文由作者三汪首發(fā)于簡(jiǎn)書。
歷史解題記錄已同步更新github.
題目
Problem Description
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.
Example
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
題目分析
題意是讓我們返回給定數(shù)組中和為目標(biāo)值的兩個(gè)元素的下標(biāo)。同時(shí)限定每個(gè)輸入都將只有一個(gè)解完箩，并且每個(gè)元素我們只能使用一次。
代碼和思路
A.原始版本
看到這個(gè)題目房揭。作為小白的我當(dāng)然是不假思索地用了窮舉法箭阶。時(shí)間復(fù)雜度O(n^2)。
好在這種粗暴的解決方案沒(méi)有像后來(lái)看到的別人說(shuō)的那樣因?yàn)闀r(shí)間復(fù)雜度太高而被leetCode拒收谚殊，
還勝過(guò)了30.2%的Java Solution丧鸯。
我認(rèn)為原因大概是因?yàn)槲矣昧藗€(gè)小聰明讓內(nèi)部循環(huán)的j=i+1而不是j=0。時(shí)
間復(fù)雜度雖然沒(méi)變嫩絮，但是實(shí)際上還是要更好一點(diǎn)的丛肢。
（如果你跟我一樣是小白，深思熟慮后還是不理解為什么這樣做剿干，給我留言呀蜂怎。我來(lái)告訴你~）
1.0版本代碼如下：
/**
*
* <p>
* Description:我自己的第一個(gè)解決方案<br />
* 耗時(shí)：39ms
* </p>
* @author wugy
* @version 0.1 2017年12月4日
* @param nums
* @param target
* @return
* int[]
*/
private int[] twoSum_1_0(int[] nums, int target) {
int[] indices =new int[2];
for (int i = 0; i < nums.length; i++) {
for (int j = i+1; j < nums.length; j++) {
if (nums[i]+nums[j]==target) {
indices[0]=i;
indices[1]=j;
return indices;
}
}
}
return null;
}
B.改進(jìn)版本
有思考才有進(jìn)步嘛。
我點(diǎn)進(jìn)了leetCode上提供的用時(shí)最少（3ms）的solution研究了一下置尔，又綜合了網(wǎng)上一些朋友的心得杠步。
(研究這道題斷斷續(xù)續(xù)的，時(shí)間跨度比較久榜轿。因此無(wú)法給出參考鏈接幽歼。只能在心里感謝一下這些朋友了)
我認(rèn)為對(duì)這個(gè)問(wèn)題最好的解決方式是使用Map來(lái)儲(chǔ)存key-value。
key是nums[]的元素谬盐，value是nums[]對(duì)應(yīng)元素的下標(biāo)甸私。
從代碼量和時(shí)間復(fù)雜度來(lái)說(shuō)，這種解決思路應(yīng)該是最優(yōu)雅的飞傀。
代碼如下：
/**
*
* <p>
* Description:研究過(guò)別人代碼以后的第二個(gè)改進(jìn)版本<br />
* 耗時(shí)：9ms
* </p>
* @author wugy
* @version 1.1 2017年12月6日
* @param nums
* @param target
* @return
* int[]
*/
private int[] twoSum_1_2(int[] nums, int target){
Map<Integer,Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int diff = target-nums[i];
if (map.containsKey(diff)) {
return new int[]{map.get(diff),i};
}
map.put(nums[i], i);
}
return null;
}
其實(shí)說(shuō)實(shí)話我不知道為什么這個(gè)1.2版本的改進(jìn)方案在leetCode上只能跑出9ms的成績(jī)皇型。
因?yàn)槲铱吹?ms的Sample Solution和我這個(gè)版本的改進(jìn)實(shí)際上是基本相同的诬烹。
leetCode告訴我我的這個(gè)版本打敗了59.65%的Java Solution。
至于其他用時(shí)比較少的Solution弃鸦，我覺(jué)得就比較扯了绞吁。
下面讓我來(lái)告訴你扯在哪里。
C.LeetCode上用時(shí)最少的Java Solution
直接來(lái)分析這個(gè)用時(shí)3ms的solution吧
/**
*
* <p>
* Description:截至此刻leetCode上的最優(yōu)解<br />
* 耗時(shí)：3ms<br />
* </p>
* 已發(fā)現(xiàn)2個(gè)無(wú)法通過(guò)的TestCase:<br />
* 1.Input:[2222222,2222222],4444444;Output:[0,1]<br />
* 2.Input:[-9,4,9,90],0;Output:[0,2]<br />
* @deprecated
* @version 0.1 2017年12月4日
* @param nums
* @param target
* @return
* int[]
*/
private int[] bestTwoSum(int[] nums, int target) {
int[] map = new int[20050];//完全無(wú)法理解為什么數(shù)組長(zhǎng)度為20050寡键。這種做法如果傳入的數(shù)組中有比20050更大的值就掛了。已向leetCode提交TestCase
int size = 4;
for (int i = 0; i < nums.length; i++) {
map[nums[i] + size] = (i + 1);
int diff = target - nums[i + 1] + size;
if (diff < 0) continue;
int d = map[diff];
if (d > 0)
return new int[]{d - 1, i + 1};
}
return null;
}
拿到這個(gè)solution的時(shí)候我是懵逼的雪隧。
因?yàn)椴恢罏槭裁磎ap[]數(shù)組定義成了20050的大小西轩，也不知道為什么要定義一個(gè)size=4。
結(jié)合自己的理解對(duì)這種進(jìn)行了重寫以后脑沿。我慢慢地理解了這個(gè)solution藕畔。
因?yàn)檫@個(gè)solution純屬扯淡。
數(shù)組定義成20050的大小應(yīng)該是因?yàn)橐延蠺estCase中nums[]元素沒(méi)有大于20050的庄拇。
size=4是因?yàn)門estCase中元素為負(fù)的的值最小為-3或-4注服。
有了size,后面代碼中if (diff < 0) continue;的這個(gè)判斷才有意義。也因此進(jìn)一步減少了耗時(shí)措近。
在上面代碼注釋中溶弟，我給出了2個(gè)無(wú)法通過(guò)的TestCase。均已提交LeetCode瞭郑。
思考
其實(shí)辜御。如果能使用int[]數(shù)組來(lái)轉(zhuǎn)換元素值與下標(biāo)，實(shí)際上是更友好的屈张。
而我們不這么做呢擒权。因?yàn)閕nt[]數(shù)組無(wú)法定義到足夠存放-2147483648到2147483647的所有int數(shù)值，會(huì)OutOfMemory阁谆。
因此只能使用HashMap來(lái)代替它碳抄。
以上。
希望我的文章對(duì)你能有所幫助场绿。
我不能保證文中所有說(shuō)法的百分百正確剖效，
但我能保證它們都是我的理解和感悟以及拒絕直接復(fù)制黏貼（確實(shí)需要引用的部分我會(huì)附上源地址）。
有什么意見(jiàn)焰盗、見(jiàn)解或疑惑贱鄙，歡迎留言討論。
