摘要：給定表，存在函數，對任意給定的關鍵字值，代入函數后若能得到包含該關鍵字的記錄在表中的地址，則稱表為哈希表，函數為哈希函數。而中的對象就是基于哈希表結構，所以我們構造一個對象即可，是當前遍歷到的值，是其與目標值的差。

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

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

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

學習算法，最直接有效的就是刷題，刷題有很多渠道，我比較推薦 LeetCode，它有國內和國外版，非常方便。現在網上有很多大牛都分享各自刷題的解法，但百讀不如一練嘛，所以我也開個【來刷LeetCode】系列，由淺入深，分享我的解法和思路，因為我的解法肯定不是最棒的，所以還會在加上我覺得優秀的解法。

嗶嗶了這么多，我們現在開擼。代碼略多，建議大家先點個贊（我就是來騙贊的~）

兩數之和，題目描述如下：

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

示例:

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

因為 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

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

這樣一來，就需要記錄差值，散列表這一數據結構就排上用場了，來看看百科關于散列表的介紹：

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

而js中的對象就是基于哈希表結構，所以我們構造一個js對象即可，value是當前遍歷到的值，key是其與目標值的差。

這是我的解法如下：

/**
 * @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)

兩數之和，題目描述如下：

給出兩個?非空 的鏈表用來表示兩個非負的整數。其中，它們各自的位數是按照?逆序?的方式存儲的，并且它們的每個節點只能存儲?一位?數字。

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

您可以假設除了數字 0 之外，這兩個數都不會以 0?開頭。

示例：

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

輸出：7 -> 0 -> 8

原因：342 + 465 = 807

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

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

將多個 ListNode 結構變成二維數組

把二維數組中的每一個下標對應的元素相加，從下標 0 開始相加，滿十進一位，算是模擬大數相加的一種簡單方式，最后輸出的是一維數組

把一維數組轉換成 ListNode 結構

我的解法如下

/**
 * 將多個ListNode結構變成二維數組，在計算該二維數組各個節點的和
 * 如傳入的兩個ListNode對象 {val:2,next:{val:3,next:null}} {val:4,next:{val:5,next:null}}
 * 轉成如下二維數組 [ [2,3], [4,5] ], 計算兩數組和 ，返回 [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);
}
/**
 * 計算數組的和
 * @param {*} list 
 */
function arraySum(list) {
    return list.reduce((result, item) => {
        return arrayItemSum(result, item);
    }, [])
}

/**
 * 計算傳入的數組的和
 * @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; //滿十進一
    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;
}

/**
 * 數組構建成 ListNode 結構
 * @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 這個求和的函數，其實，這題考的是鏈表的操作，但被我硬生生的把鏈表拆數組，最后變成了js如何實現大數相加，手動狗頭.jpg

我leetcode上看到個非常優秀的解法，在遞歸中將每個節點中的val相加，在將余數傳入遞歸函數中，直到兩個鏈表都遍歷完成

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一時苦，一直刷終會爽，加油ヾ(?°?°?)??