Javascript新法解舊題之【兩數(shù)之和】

題目如下：

給定一個(gè)整數(shù)數(shù)組和一個(gè)目標(biāo)值，找出數(shù)組中和為目標(biāo)值的兩個(gè)數(shù)。

你可以假設(shè)每個(gè)輸入只對(duì)應(yīng)一種答案，且同樣的元素不能被重復(fù)利用。

示例

給定 nums = [2, 7, 11, 15], target = 9

因?yàn)?nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

leetCood地址：兩數(shù)之和

題目不難理解，首先一上來我們馬上就能想到使用兩個(gè)循環(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;
};

兩個(gè)循環(huán)，時(shí)間復(fù)雜度為O(N*N)。

leetCode測(cè)試數(shù)據(jù)如下：

我的提交執(zhí)行用時(shí)已經(jīng)戰(zhàn)勝 17.42 % 的 javascript 提交記錄

在第二個(gè)循環(huán)中，我們只是要尋找目標(biāo)值是否在數(shù)組里，因此可想到j(luò)avascript中的一個(gè)方法----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í)際上是對(duì)數(shù)組再遍歷一次，雖然在寫法上有優(yōu)化，但是實(shí)際時(shí)間復(fù)雜度還是O(N*N)。

在時(shí)間復(fù)雜度上做優(yōu)化，我們需要解決一個(gè)問題，如何快速地在數(shù)組中檢索值？使用 indexOf 其實(shí)已經(jīng)在數(shù)據(jù)中檢索特定值的思路上了。只不過 indexOf 內(nèi)部還是對(duì)數(shù)組進(jìn)行循環(huán)檢索，因此并沒有達(dá)到更快的要求。在這方面， hash表 可以幫助到我們。

什么意思呢？比如我們有一個(gè)對(duì)象 obj = { ..., a: 1} ，當(dāng)我們?nèi)≈?Obj.a 時(shí)，是個(gè)直接尋址的過程，因此效率是很高的?；氐筋}目，在這個(gè)思路上改進(jìn)我們的代碼：

使用對(duì)象索引

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)建一個(gè)對(duì)象，并給它賦值，對(duì)象的鍵值是我們想要檢索的值，對(duì)象的值是在數(shù)組中的索引。

雖然多了創(chuàng)建對(duì)象這一過程，但是我們少了一層循環(huán)。

然后我們來看執(zhí)行效率：

我的提交執(zhí)行用時(shí)已經(jīng)戰(zhàn)勝 86.24 % 的 javascript 提交記錄。

從 17.42 % 到 86.24 %，可以說是個(gè)質(zhì)的飛躍。

es6 中，給我們提供了一個(gè)新對(duì)象 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 % 的提交。