每日一道 LeetCode (1)：兩數(shù)之和

引言

前段時間看到一篇刷 LeetCode 的文章，感觸很深，我本身自己上大學(xué)的時候，沒怎么研究過算法這一方面，導(dǎo)致自己直到現(xiàn)在算法都不咋地。

一直有心想填補(bǔ)下自己的這個短板，實(shí)際上又一直給自己找理由各種推脫。

結(jié)果今天晚上吃多了，下定決心要刷一波 LeetCode 的題，刷題的過程順便寫點(diǎn)文章分享下（其實(shí)有很好的督促作用）。

LeetCode 的背景啥的我就不多介紹了，我計劃只刷簡單難度和中等難度的題，據(jù)說刷了這兩個難度基本上就夠了，至于困難這個難度，先等我把前兩個部分刷完再說。

大致聊一下刷題的套路，先看題目， 5 分鐘左右沒思路的直接看答案，這玩意沒思路是真沒辦法，沒有基礎(chǔ)儲備想做題還是有點(diǎn)困難的。

看完答案自己動手寫一下代碼，這一點(diǎn)很重要，現(xiàn)在面試很多白板代碼，一定要自己寫，寫會有效加深記憶力。

這個系列的文章計劃日更，原本以為不是一件很難的事情，結(jié)果當(dāng)我看到了這個：

1700+ 多道題，即使刨除掉困難的部分， 2/3 也有 1000+ 道題，我真的是給自己開了一個非常棒的頭，這一下把未來兩三年的規(guī)劃都制定好了，我真是嗶了狗了。

不過不管怎么樣吧，決心都下好了，那么做還是要做的，對我這個計劃感興趣的同學(xué)可以每天在留言區(qū)和我一起打卡，預(yù)計每篇文章閱讀時長在 3 分鐘左右，寫代碼加調(diào)試代碼總時長不會超過半小時。使用的代碼為 Java ，如果使用 Python 寫的話有點(diǎn)太取巧了。

做事情，重要的是要堅持。

需要代碼朋友可以訪問我的 GitHub 和 Gitee 獲取，每天的代碼我會同步提交至這兩個代碼倉庫：

GitHub：https://github.com/meteor1993/LeetCode

Gitee：https://gitee.com/inwsy/LeetCode

題目：兩數(shù)之和

給定一個整數(shù)數(shù)組 nums 和一個目標(biāo)值 target，請你在該數(shù)組中找出和為目標(biāo)值的那兩個整數(shù)，并返回他們的數(shù)組下標(biāo)。

你可以假設(shè)每種輸入只會對應(yīng)一個答案。但是，數(shù)組中同一個元素不能使用兩遍。

示例:

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

因?yàn)?nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

思路

首先整理下思路，雖然題目的目標(biāo)是要求一個加法，使用程序直接寫加法有點(diǎn)不是那么好寫，稍微轉(zhuǎn)變一下，使用目標(biāo)值 target 減去數(shù)組 nums 中的一個值，如果得到的結(jié)果也在這個數(shù)組中，那么我們就解題完成。

暴力破解

我最先想到的也是最簡單的方案，就是暴力破解，直接兩個循環(huán)套一下，暴力去算，得到結(jié)果：

public int[] twoSum_1(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        int temp = target - nums[i];
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] == temp) {
                return new int[]{i, j};
            }
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

這種方案的缺點(diǎn)是時間復(fù)雜度有點(diǎn)高，優(yōu)點(diǎn)是簡單，應(yīng)該是每個人都能想到的方案。

因?yàn)榭偣灿?n 個元素，而對于其中的每個元素來講，我們都需要遍歷整個數(shù)組來尋找是否存在它所需要的對應(yīng)的元素，這將耗費(fèi) O(n) 的時間。

時間復(fù)雜度：? 。

空間復(fù)雜度：O(1) 。

兩次哈希表

對暴力破解方案的優(yōu)化思路是，整個數(shù)組，至少需要迭代一次，關(guān)鍵是在這次迭代中，我們要尋找另一種方案，能比套一層循環(huán)更快更高效的找到檢查在整個數(shù)組中，是否含有我們需要的值。

我們可以借助哈希表來進(jìn)行尋找，它支持以 「近似」 恒定的時間進(jìn)行快速查找。

public int[] twoSum_2(int[] nums, int target) {
    Map map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        map.put(nums[i], i);
    }
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement) && map.get(complement) != i) {
            return new int[] {i, map.get(complement)};
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

我們把包含有 n 個元素的列表遍歷兩次。由于哈希表將查找時間縮短到 O(1) ，所以時間復(fù)雜度為 O(n)。

時間復(fù)雜度：O(n) 。

空間復(fù)雜度：O(n) 。

一次哈希表：

上面我們是先把數(shù)組放到哈希表中，然后再進(jìn)行遍歷，實(shí)際上我們可以一邊放一邊進(jìn)行遍歷操作，直到某一個時刻，打成我們的目標(biāo)，這時我們可以直接返回數(shù)據(jù)，剩下沒有放到哈希表中的數(shù)據(jù)也不用再往里面放了。

public int[] twoSum_3(int[] nums, int target) {
    Map map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[] { map.get(complement), i };
        }
        map.put(nums[i], i);
    }
    throw new IllegalArgumentException("No two sum solution");
}

雖然這種方式看著比前面的兩次哈希表更加的高效，實(shí)際上時間復(fù)雜度和空間復(fù)雜度是一致的，同樣是：

時間復(fù)雜度：O(n) 。

空間復(fù)雜度：O(n) 。