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

一、前言

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

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

對(duì)于這個(gè)算法題來(lái)說(shuō)我還是蠻喜歡的，因?yàn)槲沂菍儆谀欠N很偏科的男人，通常數(shù)學(xué)：140分，英語(yǔ)：40分(當(dāng)年)。好！理由找好了，開(kāi)始刷個(gè)題。聽(tīng)說(shuō)數(shù)學(xué)好的男人都不簡(jiǎn)單！ 所以我打算接下來(lái)定期的做一些算法題，同時(shí)將我的思路進(jìn)行整理，寫(xiě)成筆記分享給新人，一起從算法中成長(zhǎng)。

二、時(shí)間復(fù)雜度

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

1. O(n)

代碼塊

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

最終耗時(shí)：

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

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

所謂低階項(xiàng)，簡(jiǎn)單地說(shuō)就是當(dāng)n非常大時(shí)，這個(gè)項(xiàng)相對(duì)于另外一個(gè)項(xiàng)很小，可以忽略，比如n相對(duì)于n^2,n就是低階項(xiàng)

2. O(logn)

代碼塊

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

最終耗時(shí)：

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

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

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

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

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

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

示例:

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

java

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

四、解題

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

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

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

可以看到這樣的時(shí)間復(fù)雜度是；n*(n-1) ··· 4*3、4*2、4*1，也就是O(n^2)，有點(diǎn)像九九乘法表的結(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;
}

耗時(shí)：

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

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

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

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

代碼：

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};
}

耗時(shí)：

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

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

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

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

• 這個(gè)2048是我們?cè)嚦鰜?lái)的，主要根據(jù)leetcode中的單測(cè)用例決定。

耗時(shí)：

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

五、總結(jié)

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