前段時(shí)間岔留，有次面試中遇到一道算法題，感覺答的不是很好检柬，后面查相關(guān)資料發(fā)現(xiàn)竟然就是LeeCode上的原題献联。。厕吉。
題目是這樣的，給定一個(gè)int數(shù)組械念，和target目標(biāo)值头朱，要求返回?cái)?shù)組中兩個(gè)數(shù)加起來等于target的這兩個(gè)元素的下標(biāo)，可以明確只會(huì)有一對(duì)能匹配上龄减。
// 例如项钮，給定：
int[] arr = new int[] { 1, 2, 3, 4, 7, 9, 8 };
int target = 13;
// 返回：3, 5
面試官問我題目理解清楚了嗎？我心想：這還不簡(jiǎn)單希停，不就是兩層循環(huán)判斷一下就可以了嘛烁巫！于是二話不說，啪啪幾分鐘就寫出了下面這段代碼宠能。
public int[] sum(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
if ((arr[i] + arr[j]) == target) {
return new int[] { i, j };
}
}
}
return null;
}
給面試官看后亚隙，問我這種實(shí)現(xiàn)的時(shí)間復(fù)雜度是多少？我說最壞的情況應(yīng)該是O(n2)违崇。他問還有其它更快的實(shí)現(xiàn)方式嗎阿弃？讓我再想想。
看來他對(duì)我這個(gè)實(shí)現(xiàn)不是很滿意羞延，也是渣淳，咋可能有這么簡(jiǎn)單的題，然而想了幾分鐘后還是一點(diǎn)頭緒沒有伴箩。入愧。。
最后面試掛了，不知道是不是掛在這道題上棺蛛。后來無意中在LeeCode上看到原題才恍然大悟Ｕ觥！鞠值！
其實(shí)就是以空間換時(shí)間媚创，用HashMap把數(shù)存起來，通過Hash查找方式減少一層遍歷彤恶，因?yàn)镠ash理論上時(shí)間負(fù)責(zé)度是O(1)钞钙，從而將總的時(shí)間復(fù)雜度從O(n2)降到O(n)。
附LeeCode上的答案：
public int[] sum(int[] arr, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
map.put(arr[i], i);
}
for (int i = 0; i < arr.length; i++) {
int complement = target - arr[i];
if (map.containsKey(complement) && map.get(complement) != i) {
return new int[] { i, map.get(complement) };
}
}
return null;
}
更簡(jiǎn)便的寫法：
public int[] sum(int[] arr, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
int complement = target - arr[i];
if (map.containsKey(complement)) {
return new int[] { map.get(complement), i };
}
map.put(arr[i], i);
}
return null;
}
看來以后有時(shí)間還是要看看算法声离，不僅是為了面試芒炼，實(shí)際項(xiàng)目中也會(huì)遇到的，要寫出高性能的程序术徊，還是要靠這些本刽。
