摘要：給定表，存在函數(shù)，對任意給定的關(guān)鍵字值，代入函數(shù)后若能得到包含該關(guān)鍵字的記錄在表中的地址，則稱表為哈希表，函數(shù)為哈希函數(shù)。而中的對象就是基于哈希表結(jié)構(gòu)，所以我們構(gòu)造一個(gè)對象即可，是當(dāng)前遍歷到的值，是其與目標(biāo)值的差。

大部分玩前端的小伙伴，在算法上都相對要薄弱些，畢竟調(diào)樣式、調(diào)兼容就夠掉頭發(fā)的了，哪還有多余的頭發(fā)再去折騰。

確實(shí)在前端中需要使用到算法的地方是比較少，但若要往高級方向發(fā)展，算法的基本功就非常重要啦。對了，算法在面試中可是必考項(xiàng)啊，所以為了期望薪資，頭發(fā)還是得做下犧牲呀。

有些小伙伴認(rèn)為，刷了那些奇奇怪怪的算法題，可在工作中很少能直接派上用場，嗯，沒錯(cuò)，所以學(xué)算法是件高延遲滿足的事情。那么學(xué)算法，到底收獲什么呢？我覺得通過練習(xí)算法，培養(yǎng)我們解決問題的潛意識才是最重要的。

學(xué)習(xí)算法，最直接有效的就是刷題，刷題有很多渠道，我比較推薦 LeetCode，它有國內(nèi)和國外版，非常方便。現(xiàn)在網(wǎng)上有很多大牛都分享各自刷題的解法，但百讀不如一練嘛，所以我也開個(gè)【來刷LeetCode】系列，由淺入深，分享我的解法和思路，因?yàn)槲业慕夥隙ú皇亲畎舻模赃€會在加上我覺得優(yōu)秀的解法。

嗶嗶了這么多，我們現(xiàn)在開擼。代碼略多，建議大家先點(diǎn)個(gè)贊（我就是來騙贊的~）

兩數(shù)之和，題目描述如下：

給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)目標(biāo)值 target，請你在該數(shù)組中找出和為目標(biāo)值的那 兩個(gè) 整數(shù)，并返回他們的數(shù)組下標(biāo)。
你可以假設(shè)每種輸入只會對應(yīng)一個(gè)答案。但是，你不能重復(fù)利用這個(gè)數(shù)組中同樣的元素。

示例:

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

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

所以返回 [0, 1]

這題，最暴力的解法就是逐個(gè)循環(huán)查找，但時(shí)間復(fù)雜度是 n*n ，太暴力的不適合我們。
可以這么看，在遍歷第一個(gè)值得時(shí)候，保留這個(gè)值與target的差，然后在下次遍歷中，看看是不是與保留的差值相同，如果相同，那么就可以找到我們想要的結(jié)果了。畫個(gè)簡單的表格如下：

這樣一來，就需要記錄差值，散列表這一數(shù)據(jù)結(jié)構(gòu)就排上用場了，來看看百科關(guān)于散列表的介紹：

散列表（Hash table，也叫哈希表），是根據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)。也就是說，它通過把關(guān)鍵碼值映射到表中一個(gè)位置來訪問記錄，以加快查找的速度。這個(gè)映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表。
給定表M，存在函數(shù)f(key)，對任意給定的關(guān)鍵字值key，代入函數(shù)后若能得到包含該關(guān)鍵字的記錄在表中的地址，則稱表M為哈希(Hash）表，函數(shù)f(key)為哈希(Hash) 函數(shù)。

而js中的對象就是基于哈希表結(jié)構(gòu)，所以我們構(gòu)造一個(gè)js對象即可，value是當(dāng)前遍歷到的值，key是其與目標(biāo)值的差。

這是我的解法如下：

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
    let map = {};
    let result = []
    for (let index = 0;index <= nums.length;index++) {
        const val = nums[index];
        if (map[val] !== undefined) {
            result.push(map[val], index);
            break;
        }
        const a = target - val;
        map[a] = index
    }
    return result;
};

// nums = [2, 6, 3, 15], target = 9
// twoSum(nums,target)

兩數(shù)之和，題目描述如下：

給出兩個(gè)?非空 的鏈表用來表示兩個(gè)非負(fù)的整數(shù)。其中，它們各自的位數(shù)是按照?逆序?的方式存儲的，并且它們的每個(gè)節(jié)點(diǎn)只能存儲?一位?數(shù)字。

如果，我們將這兩個(gè)數(shù)相加起來，則會返回一個(gè)新的鏈表來表示它們的和。

您可以假設(shè)除了數(shù)字 0 之外，這兩個(gè)數(shù)都不會以 0?開頭。

示例：

輸入：(2 -> 4 -> 3) + (5 -> 6 -> 4)

輸出：7 -> 0 -> 8

原因：342 + 465 = 807

看到這題，我的第一想法就是把鏈表的每個(gè)節(jié)點(diǎn)的值合并成一個(gè)整形，然后在相加，最后在轉(zhuǎn)換成鏈表，思路非常簡單暴力。可等我寫完，測試用例一跑，結(jié)果如下

原因是 JavaScript 中Number的精度是16位，超過了就會出現(xiàn)精讀丟失，看來直接轉(zhuǎn)換然后相加的方式不行啊，沒關(guān)系，那就用數(shù)組模擬大數(shù)相加。完整的步驟如下

將多個(gè) ListNode 結(jié)構(gòu)變成二維數(shù)組

把二維數(shù)組中的每一個(gè)下標(biāo)對應(yīng)的元素相加，從下標(biāo) 0 開始相加，滿十進(jìn)一位，算是模擬大數(shù)相加的一種簡單方式，最后輸出的是一維數(shù)組

把一維數(shù)組轉(zhuǎn)換成 ListNode 結(jié)構(gòu)

我的解法如下

/**
 * 將多個(gè)ListNode結(jié)構(gòu)變成二維數(shù)組，在計(jì)算該二維數(shù)組各個(gè)節(jié)點(diǎn)的和
 * 如傳入的兩個(gè)ListNode對象 {val:2,next:{val:3,next:null}} {val:4,next:{val:5,next:null}}
 * 轉(zhuǎn)成如下二維數(shù)組 [ [2,3], [4,5] ], 計(jì)算兩數(shù)組和 ，返回 [6,8]
 * @param  {...any} list 
 */
function addListNode(...list) {
    const valList = list.map((node) => {
        const list = [];
        while (node) {
            list.push(Number(node.val));
            node = node.next;
        }
        return list;
    })
    return arraySum(valList);
}
/**
 * 計(jì)算數(shù)組的和
 * @param {*} list 
 */
function arraySum(list) {
    return list.reduce((result, item) => {
        return arrayItemSum(result, item);
    }, [])
}

/**
 * 計(jì)算傳入的數(shù)組的和
 * @param {Array} a 
 * @param {Array} b 
 */
function arrayItemSum(a, b) {
    let logArray = a;
    let sortArray = b;
    if (b.length > a.length) {
        logArray = b;
        sortArray = a;
    }
    let addOne = 0; //滿十進(jìn)一
    const result = logArray.reduce((result, val, index) => {
        const sum = (result[index] || 0) + val + addOne;
        addOne = 1;
        const mod = sum % 10;
        const div = sum / 10;
        if (div < 1) {
            result[index] = mod;
            addOne = 0;
        } else if (div > 1) {
            result[index] = mod;
        } else {
            result[index] = 0;
        }
        return result;
    }, sortArray)
    if(addOne){
        result.push(1);
    }
    if (!result[result.length - 1]) {
        result.pop(1)
    }
    return result;
}

/**
 * 數(shù)組構(gòu)建成 ListNode 結(jié)構(gòu)
 * @param {*} numList 
 */
function numToListNode(numList) {
    let preNode = undefined;
    return numList.reduce((result, val) => {
        let node = new ListNode(val);
        if (preNode) {
            preNode.next = node;
            preNode = node
        } else {
            result = preNode = node
        }
        return result
    }, new ListNode(0))
}
var addTwoNumbers = function (l1, l2) {
    return numToListNode(addListNode(l1, l2));
};

看完代碼，大家是不是覺得代碼非常長，尤其是 arrayItemSum 這個(gè)求和的函數(shù)，其實(shí)，這題考的是鏈表的操作，但被我硬生生的把鏈表拆數(shù)組，最后變成了js如何實(shí)現(xiàn)大數(shù)相加，手動(dòng)狗頭.jpg

我leetcode上看到個(gè)非常優(yōu)秀的解法，在遞歸中將每個(gè)節(jié)點(diǎn)中的val相加，在將余數(shù)傳入遞歸函數(shù)中，直到兩個(gè)鏈表都遍歷完成

var addTwoNumbers = function(l1, l2) {
    const addNumbers = (l1, l2, extra) => {
        let sum = (l1 ? l1.val : 0) + (l2 ? l2.val : 0) + extra;
        const node = new ListNode(sum % 10);
        let nl1 = l1 ? l1.next : null;
        let nl2 = l2 ? l2.next : null;
        if (nl1 || nl2 || sum > 9) {
            node.next = addNumbers(nl1, nl2, Math.floor(sum / 10))
        }
        return node;
    };
    return addNumbers(l1, l2, 0);
};

刷leetcode一時(shí)苦，一直刷終會爽，加油ヾ(?°?°?)??