Github： https://github.com/MyGitBooks/niubility-algorithm
本文檔是作者小傅哥通過從leetcode 劍指offer 編程之美 等資料中收集算法題目并加以邏輯分析和編碼搞定題目，最終編寫資料到本文檔中，為大家提供在算法領(lǐng)域的幫助。如果本文能為您提供幫助，請給予支持(加入、點贊、分享)！

一、前言

在這之前我基本沒怎么關(guān)注過leetcode，還是最近有人經(jīng)常說面試刷題，算法刷到谷歌上班去了。我才開始了解下，仔細(xì)一看原來雖然沒關(guān)注過，但是類似的題還是做過的并且還買過一本《編程之美》的書。

在 中每個算法題都有編號；1 2 3 ... 1566，而且還在增加。你我都是新人，既然沒了解過那就從第一題開始吧，嘗試從算法中吸取一些創(chuàng)新的思路。否則為什么那么多公司面試招聘都會去考下算法！谷歌``````字節(jié)跳動``````騰訊``````阿里``````等等

對于這個算法題來說我還是蠻喜歡的，因為我是屬于那種很偏科的男人，通常數(shù)學(xué)：140分，英語：40分(當(dāng)年)。好！理由找好了，開始刷個題。聽說數(shù)學(xué)好的男人都不簡單！ 所以我打算接下來定期的做一些算法題，同時將我的思路進行整理，寫成筆記分享給新人，一起從算法中成長。

二、時間復(fù)雜度

時間復(fù)雜度可以說是算法的基礎(chǔ)，如果不在乎時間復(fù)雜度，那么沒有 for循環(huán)解決不了問題！而我們一般所說的時間復(fù)雜度以及耗時排列包括；O(1)<>O(logn)<>O(n)<>O(nlogn)<>O(n^2)<>O(n^3)<>O(2^n)<>O(n!)<>O(n^n)等。那么一段代碼的耗時主要由各個行為塊的執(zhí)行次數(shù)相加并去掉最小影響系數(shù)而得出的，接下來先看下這種東西是如何計算出來的。

1. O(n)

代碼塊

int n = 10;
for (int i = 0; i  n; i++) {
    System.out.println(i);
}

最終耗時：

sum = 1 + 1 + n + 1+ n + n
= 3n+3
= n (忽略低階梯)

從公式和象限圖中可以看到，當(dāng)我們的公式3n+3，隨著 n 的數(shù)值越來越大的時候，常數(shù)3就可以忽略低階梯不記了。所以在這段代碼中的時間復(fù)雜度就是；O(n)

所謂低階項，簡單地說就是當(dāng)n非常大時，這個項相對于另外一個項很小，可以忽略，比如n相對于n^2,n就是低階項

2. O(logn)

代碼塊

int sum = 1, n = 10;
while (sum  n) {
    sum = sum * 2;
}

最終耗時：

這回我們只看執(zhí)行次數(shù)最多的，很明顯這是一個 2 * 2 * 2 ··· n，大于 n 跳出循環(huán)。
那么我們使用函數(shù)；2^x = n，x = logn，就可以表示出整體的時間復(fù)雜度為 O(logn)

好！結(jié)合這兩個例子，相信你對時間復(fù)雜度已經(jīng)有所理解，后面的算法題中就可以知道自己的算法是否好壞。

三、算法題：兩數(shù)之和

https:///problems/two-sum/submissions/

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

你可以假設(shè)每種輸入只會對應(yīng)一個答案。但是，你不能重復(fù)利用這個數(shù)組中同樣的元素。

示例:

給定 nums = [2, 7, 11, 15], target = 9
 
因為 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

java

class Solution {
    public int[] twoSum(int[] nums, int target) {
// todo
    }
}

四、解題

這是leetcode的第一題，難度簡單，其實如果要是使用兩層for循環(huán)嵌套，確實不太難。但是如果想打敗99%的選手還是需要斟酌斟酌算法。

思路1，雙層循環(huán)

先不考慮時間復(fù)雜度的話，最直接的就是雙層for循環(huán)，用每一個數(shù)和數(shù)組中其他數(shù)做家和比對，如下；

可以看到這樣的時間復(fù)雜度是；n*(n-1) ··· 4*3、4*2、4*1，也就是O(n^2)，有點像九九乘法表的結(jié)構(gòu)。

代碼：

public int[] twoSum(int[] nums, int target) {
    int[] idxs = new int[2];
    for (int i = 0; i  nums.length; i++) {
        for (int j = i + 1; j  nums.length; j++) {
            if (nums[i] + nums[j] == target) {
                idxs[0] = i;
                idxs[1] = j;
            }
        }
    }
    return idxs;
}

耗時：

• 對于這樣的算法雖然能解決問題，但是并不能滿足我們的需求，畢竟這個級別的時間復(fù)雜度下實在是太慢了。

思路2，單層循環(huán)

為了把這樣一個雙層循環(huán)簡化為單層，我們最能直接想到的就事放到 Map 這樣的數(shù)據(jù)結(jié)構(gòu)中，方便我們存取比對。那么這樣的一個計算過程如下圖；

• 這個過程的核心內(nèi)容是將原來的兩數(shù)之和改成差值計算，并將每次的差與 Map 中元素進行比對。如果差值正好存在 Map 中，那么直接取出。否則將數(shù)存入到 Map 中，繼續(xù)執(zhí)行。
• 這個過程就可以將原來的雙層循環(huán)改為單層，時間復(fù)雜度也到了 O(n) 級別。

代碼：

public static int[] twoSum(int[] nums, int target) {
    MapInteger, Integer> hashMap = new HashMapInteger, Integer>(nums.length);
    for (int i = 0; i  nums.length; i++) {
        if (hashMap.containsKey(target - nums[i])) {
            return new int[]{hashMap.get(target - nums[i]), i};
        }
        hashMap.put(nums[i], i);
    }
    return new int[]{-1, -1};
}

耗時：

• 可以看到當(dāng)我們使用 Map 結(jié)構(gòu)的時候，整個執(zhí)行執(zhí)行用時已經(jīng)有了很大的改善。但是你有考慮過containsKey與 get是否為 null 相比哪個快嗎？
• 這個算法已經(jīng)很良好了，但是這個對 key 值的比對還是很耗時的，需要反復(fù)的對 map 進行操作，那么我們還需要再優(yōu)化一下。

思路3，Bit結(jié)構(gòu)

如果說想把我們上面使用 Map 結(jié)構(gòu)的地方優(yōu)化掉，我們可以考慮下 Map 數(shù)據(jù)是如何存放的，他有一種算法是自身擴容 2^n - 1 & 元素，求地址。之后按照地址在進行存放數(shù)據(jù)。那么我們可以把這部分算法拿出來，我們自己設(shè)計一個數(shù)組結(jié)構(gòu)，將元素進行與運算存放到我們自己定義的數(shù)組中。如下圖；

• 左側(cè)是我們假定的入?yún)?code>int[] nums，32是我們設(shè)定的值，這個值的設(shè)定需要滿足存放大小夠用，否則地址會混亂。
• 接下來我們使用 32 - 1，也就是二進制 011111與每一個數(shù)組中的值進行與運算，求存放地址。
• 當(dāng)算好地址后，將元素存放在數(shù)組中，設(shè)置值。這個值就是我們的元素本身位置了，但是需要+1，因為默認(rèn)數(shù)組是0，如果不加1，就看不到位置了。最終使用的時候，可以再將位置結(jié)果 -1。

代碼：

public static int[] towSum(int[] nums, int target) {
    int volume = 2048;              
    int bitMode = volume - 1;       
    int[] t = new int[volume];      
    for (int i = 0; i  nums.length; i++) {
        int c = (target - nums[i]) & bitMode;
        if (t[c] != 0) return new int[]{t[c] - 1, i};
        t[nums[i] & bitMode] = i + 1;
    }
    return new int[]{-1, -1};
}

• 這個2048是我們試出來的，主要根據(jù)leetcode中的單測用例決定。

耗時：

• 出現(xiàn)0毫秒耗時，100%擊敗，這個不一定每次都這樣，可能你試的時候不一樣。得益于數(shù)據(jù)結(jié)構(gòu)的優(yōu)化使得這個算法的耗時很少。

五、總結(jié)

• 野路子搞算法，沒有看過算法導(dǎo)論、也沒有套用模板，但如果需要后續(xù)的不斷的加深自己的知識點，也是需要學(xué)習(xí)的。目前在我看來這些更像是數(shù)學(xué)題，主要可以提升對同一件事情的多種處理方式，同時也增加個人的編程能力。
• 算法的學(xué)習(xí)也不太應(yīng)該套用各種理論，當(dāng)然每個人看法不一樣，我允許你的觀點，也要接受我的想法。
• 在各個大廠面試過程中，都有；算法、源碼、項目、技術(shù)棧以及個人的一些優(yōu)點，如果你能在前兩個點上給面試官很好的印象，那么你就放心的要工資吧。
• 從這篇文章開始，我會陸續(xù)做一做算法題，提升自己的功夫底子，也分析給小白。歡迎小白跟隨！Git地址：https://github.com/MyGitBooks/niubility-algorithm