本文由作者三汪首發(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)。
好在這種粗暴的解決方案沒有像后來看到的別人說的那樣因?yàn)闀r(shí)間復(fù)雜度太高而被leetCode拒收，
還勝過了30.2%的Java Solution。
我認(rèn)為原因大概是因?yàn)槲矣昧藗€(gè)小聰明讓內(nèi)部循環(huán)的j=i+1而不是j=0。時(shí)
間復(fù)雜度雖然沒變，但是實(shí)際上還是要更好一點(diǎn)的。
（如果你跟我一樣是小白，深思熟慮后還是不理解為什么這樣做，給我留言呀。我來告訴你~）
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í)間跨度比較久。因此無法給出參考鏈接。只能在心里感謝一下這些朋友了)
我認(rèn)為對(duì)這個(gè)問題最好的解決方式是使用Map來儲(chǔ)存key-value。
key是nums[]的元素，value是nums[]對(duì)應(yīng)元素的下標(biāo)。
從代碼量和時(shí)間復(fù)雜度來說，這種解決思路應(yīng)該是最優(yōu)雅的。
代碼如下：
/**
*
* <p>
* Description:研究過別人代碼以后的第二個(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í)說實(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，我覺得就比較扯了。
下面讓我來告訴你扯在哪里。
C.LeetCode上用時(shí)最少的Java Solution
直接來分析這個(gè)用時(shí)3ms的solution吧
/**
*
* <p>
* Description:截至此刻leetCode上的最優(yōu)解<br />
* 耗時(shí)：3ms<br />
* </p>
* 已發(fā)現(xiàn)2個(gè)無法通過的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];//完全無法理解為什么數(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[]元素沒有大于20050的。
size=4是因?yàn)門estCase中元素為負(fù)的的值最小為-3或-4。
有了size,后面代碼中if (diff < 0) continue;的這個(gè)判斷才有意義。也因此進(jìn)一步減少了耗時(shí)。
在上面代碼注釋中，我給出了2個(gè)無法通過的TestCase。均已提交LeetCode。
思考
其實(shí)。如果能使用int[]數(shù)組來轉(zhuǎn)換元素值與下標(biāo)，實(shí)際上是更友好的。
而我們不這么做呢。因?yàn)閕nt[]數(shù)組無法定義到足夠存放-2147483648到2147483647的所有int數(shù)值，會(huì)OutOfMemory。
因此只能使用HashMap來代替它。
以上。
希望我的文章對(duì)你能有所幫助。
我不能保證文中所有說法的百分百正確，
但我能保證它們都是我的理解和感悟以及拒絕直接復(fù)制黏貼（確實(shí)需要引用的部分我會(huì)附上源地址）。
有什么意見、見解或疑惑，歡迎留言討論。
