Javascript新法解舊題之【兩數(shù)之和】
題目如下：
給定一個整數(shù)數(shù)組和一個目標(biāo)值嫌变，找出數(shù)組中和為目標(biāo)值的兩個數(shù)吨艇。
你可以假設(shè)每個輸入只對應(yīng)一種答案，且同樣的元素不能被重復(fù)利用腾啥。
示例
給定 nums = [2, 7, 11, 15], target = 9
因為 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
leetCood地址：兩數(shù)之和
題目不難理解东涡，首先一上來我們馬上就能想到使用兩個循環(huán)解決的辦法。
遍歷所有組合倘待，找到符合要求的組合就行疮跑。
雙層循環(huán)
代碼如下：
const twoSum = (nums, target) => {
let arr = [];
for(let i = 0; i < nums.length; i++) {
for(let j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] === target) {
arr = [i, j];
break;
}
}
}
return arr;
};
兩個循環(huán)，時間復(fù)雜度為O(N*N)凸舵。
leetCode測試數(shù)據(jù)如下：
我的提交執(zhí)行用時已經(jīng)戰(zhàn)勝 17.42 % 的 javascript 提交記錄
在第二個循環(huán)中祖娘，我們只是要尋找目標(biāo)值是否在數(shù)組里，因此可想到j(luò)avascript中的一個方法----indexOf啊奄。
indexOf 用法
代碼可改寫如下：
const twoSum = (nums, target) => {
let a, b;
for(let i = 0; i < nums.length; i++) {
b = nums.indexOf(target - nums[i]);
if(b > -1 && b !== i) {
a = i;
break;
}
}
return [a, b];
};
但是 Array 的 indexOf 方法實際上是對數(shù)組再遍歷一次渐苏，雖然在寫法上有優(yōu)化，但是實際時間復(fù)雜度還是O(N*N)菇夸。
在時間復(fù)雜度上做優(yōu)化琼富，我們需要解決一個問題，如何快速地在數(shù)組中檢索值庄新？使用 indexOf 其實已經(jīng)在數(shù)據(jù)中檢索特定值的思路上了鞠眉。只不過 indexOf 內(nèi)部還是對數(shù)組進行循環(huán)檢索薯鼠，因此并沒有達到更快的要求。在這方面械蹋， hash表 可以幫助到我們出皇。
什么意思呢？比如我們有一個對象 obj = { ..., a: 1} 朝蜘，當(dāng)我們?nèi)≈?Obj.a 時恶迈，是個直接尋址的過程，因此效率是很高的谱醇∠局伲回到題目，在這個思路上改進我們的代碼：
使用對象索引
const twoSum = (nums, target) => {
let mapObj = {};
let res = [];
nums.forEach((e, i) => mapObj[e] = i);
for(let i=0;i<nums.length;i++) {
let j = mapObj[targer - nums[i]];
if(j && j !== i) {
res = [i, j];
break;
}
}
return res;
};
我們創(chuàng)建一個對象副渴，并給它賦值奈附，對象的鍵值是我們想要檢索的值，對象的值是在數(shù)組中的索引煮剧。
雖然多了創(chuàng)建對象這一過程斥滤，但是我們少了一層循環(huán)。
然后我們來看執(zhí)行效率：
我的提交執(zhí)行用時已經(jīng)戰(zhàn)勝 86.24 % 的 javascript 提交記錄勉盅。
從 17.42 % 到 86.24 %佑颇，可以說是個質(zhì)的飛躍。
es6 中草娜，給我們提供了一個新對象 Map挑胸，在這里就可以拍上用途。
使用 map
const twoSum = (nums, target) => {
let map = new Map();
let res = [];
nums.forEach((e, i) => map.set(e, i));
for(let i=0;i<nums.length;i++) {
let j = map.get[targer - nums[i]];
if(j && j !== i) {
res = [i, j];
break;
}
}
return res;
};
最終使用 Map 優(yōu)化的代碼宰闰，讓我們戰(zhàn)勝了 97.21 % 的提交茬贵。
