2023算法與數(shù)據(jù)結(jié)構(gòu)解析

算法與數(shù)據(jù)結(jié)構(gòu)解析2023目錄TOC\o"1-1"\h\u9843第一章課程簡(jiǎn)介及算法復(fù)雜度分析 316882第二章數(shù)組問(wèn)題講解 35428第三章二分查找相關(guān)問(wèn)題講解 49439第四章字符串問(wèn)題講解 410614第五章滑動(dòng)窗口相關(guān)問(wèn)題講解 420766第六章鏈表問(wèn)題講解 42382第七章哈希表相關(guān)題目講解 59462第八章棧和隊(duì)列問(wèn)題講解 520555第九章排序相關(guān)問(wèn)題講解 612945第十章二叉樹(shù)和遞歸問(wèn)題講解 6349第十一章貪心算法講解 73278第十二章動(dòng)態(tài)規(guī)劃講解 714574第十三章回溯算法講解 826472第十四章深度優(yōu)先搜索和廣度優(yōu)先搜索講解 810459第十五章位運(yùn)算和數(shù)學(xué)方法講解 93472算法和數(shù)據(jù)結(jié)構(gòu)解析 930004第一章算法簡(jiǎn)介 92611第二章數(shù)組問(wèn)題講解 1632738第三章二分查找相關(guān)問(wèn)題講解 4130587第四章字符串問(wèn)題講解 5525262第五章滑動(dòng)窗口相關(guān)問(wèn)題講解 6722350第六章鏈表問(wèn)題講解 924661第七章哈希表相關(guān)問(wèn)題講解 1029434第八章棧和隊(duì)列相關(guān)問(wèn)題講解 11914800第九章排序相關(guān)問(wèn)題講解 1473951第十章二叉樹(shù)及遞歸問(wèn)題講解 1678064第十一章貪心算法講解 1884403第十二章動(dòng)態(tài)規(guī)劃講解 2076226第十三章回溯算法講解 23326747第十四章深度優(yōu)先搜索和廣度優(yōu)先搜索 2486369第十五章位運(yùn)算和數(shù)學(xué)方法講解 265第一章課程簡(jiǎn)介及算法復(fù)雜度分析數(shù)據(jù)結(jié)構(gòu)與算法概述算法復(fù)雜度的概念大O表示法算法分類(lèi)常見(jiàn)經(jīng)典算法第二章數(shù)組問(wèn)題講解題目：兩數(shù)之和題目：三數(shù)之和題目：下一個(gè)排列題目：旋轉(zhuǎn)圖像第三章二分查找相關(guān)問(wèn)題講解程序員任何時(shí)候都必須能夠手寫(xiě)的二分查找，還有很多常見(jiàn)變種。二分查找理論講解二分查找代碼實(shí)現(xiàn)復(fù)雜度分析力扣真題講解題目：搜索二維矩陣題目：尋找重復(fù)數(shù)第四章字符串問(wèn)題講解題目：字符串相加題目：字符串相乘題目：去除重復(fù)字母第五章滑動(dòng)窗口相關(guān)問(wèn)題講解TCP/IP中的握手機(jī)制的實(shí)現(xiàn)就用到了滑動(dòng)窗口。一般結(jié)合數(shù)組或者字符串?dāng)?shù)據(jù)結(jié)構(gòu)使用。力扣真題講解題目：滑動(dòng)窗口最大值題目：最小覆蓋子串題目：找到字符串中所有字母異位詞第六章鏈表問(wèn)題講解鏈表數(shù)據(jù)結(jié)構(gòu)非常常見(jiàn)，比如操作系統(tǒng)的內(nèi)存分配的原理。鏈表數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)單向鏈表雙向鏈表循環(huán)鏈表力扣真題講解題目：反轉(zhuǎn)鏈表題目：合并兩個(gè)有序鏈表題目：刪除鏈表的倒數(shù)第N個(gè)節(jié)點(diǎn)第七章哈希表相關(guān)題目講解無(wú)處不在的哈希表，最經(jīng)典的例子：JSON數(shù)據(jù)結(jié)構(gòu)。哈希表數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)哈希表代碼Java實(shí)現(xiàn)哈希表時(shí)間與空間復(fù)雜度分析力扣真題講解題目：只出現(xiàn)一次的數(shù)字題目：最長(zhǎng)連續(xù)序列題目：LRU緩存機(jī)制第八章棧和隊(duì)列問(wèn)題講解棧和隊(duì)列在計(jì)算機(jī)科學(xué)中也是無(wú)處不在的，如函數(shù)調(diào)用棧、優(yōu)先隊(duì)列等等。棧和隊(duì)列數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)復(fù)習(xí)棧的Java代碼實(shí)現(xiàn)隊(duì)列的Java代碼實(shí)現(xiàn)優(yōu)先隊(duì)列數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)雙向隊(duì)列（雙端隊(duì)列）數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)復(fù)雜度分析力扣真題講解題目：使用棧實(shí)現(xiàn)隊(duì)列題目：有效的括號(hào)題目：柱狀圖中最大的矩形第九章排序相關(guān)問(wèn)題講解作為程序員必須掌握的排序算法：冒泡排序，插入排序，快速排序，歸并排序，堆排序，桶排序。排序相關(guān)算法復(fù)習(xí)插入排序冒泡排序快速排序歸并排序堆排序桶排序力扣真題講解題目：數(shù)組中的第K個(gè)最大元素題目：顏色分類(lèi)題目：合并區(qū)間第十章二叉樹(shù)和遞歸問(wèn)題講解作為一個(gè)程序員，必須掌握遞歸思想，而二叉樹(shù)是理解遞歸最好的途徑。而且，樹(shù)形結(jié)構(gòu)在計(jì)算機(jī)中也是隨處可見(jiàn)，比如DOM樹(shù)、目錄樹(shù)等。樹(shù)形數(shù)據(jù)結(jié)構(gòu)分析二叉樹(shù)二叉搜索樹(shù)B樹(shù)、B+樹(shù)AVL樹(shù)和紅黑樹(shù)復(fù)雜度分析力扣真題講解題目：翻轉(zhuǎn)二叉樹(shù)題目：平衡二叉樹(shù)題目：驗(yàn)證二叉搜索樹(shù)第十一章貪心算法講解貪心算法理論講解貪心算法原理以哈夫曼編碼為例子講解貪心算法背包問(wèn)題簡(jiǎn)介力扣真題講解題目：跳躍游戲題目：跳躍游戲II題目：任務(wù)調(diào)度器第十二章動(dòng)態(tài)規(guī)劃講解很多同學(xué)會(huì)覺(jué)得“動(dòng)態(tài)規(guī)劃”很難，我們?cè)诒菊n程中，將會(huì)徹底理解動(dòng)態(tài)規(guī)劃。動(dòng)態(tài)規(guī)劃理論講解動(dòng)態(tài)規(guī)劃原理動(dòng)態(tài)規(guī)劃的步驟斐波那契數(shù)列背包問(wèn)題講解力扣真題講解題目：最長(zhǎng)公共子序列題目：不同的二叉搜索樹(shù)題目：買(mǎi)賣(mài)股票的最佳時(shí)機(jī)題目：爬樓梯題目：打家劫舍題目：零錢(qián)兌換第十三章回溯算法講解回溯算法在面試一些大廠時(shí)，是很常見(jiàn)的題目。著名的“八皇后”問(wèn)題就是回溯算法的最著名的例子?；厮菟惴ㄖv解以八皇后為例講解力扣真題講解題目：全排列題目：括號(hào)生成題目：電話(huà)號(hào)碼的字母組合第十四章深度優(yōu)先搜索和廣度優(yōu)先搜索講解DFS、BFS在面試一些大廠時(shí)，也是很常見(jiàn)的題目。對(duì)于數(shù)結(jié)構(gòu)的遍歷，DFS和BFS是最常用的做法。DFS、BFS講解DFS和BFS時(shí)間復(fù)雜度和空間復(fù)雜度分析遞歸實(shí)現(xiàn)講解非遞歸實(shí)現(xiàn)講解力扣真題講解題目：?jiǎn)卧~搜索題目：二叉樹(shù)的序列化與反序列化題目：課程表第十五章位運(yùn)算和數(shù)學(xué)方法講解位運(yùn)算基礎(chǔ)知識(shí)講解計(jì)算機(jī)底層的二進(jìn)制表示位運(yùn)算符講解進(jìn)制轉(zhuǎn)換講解位運(yùn)算實(shí)現(xiàn)海量數(shù)據(jù)去重力扣真題講解題目：2的冪題目：漢明距離題目：可憐的小豬題目：雞蛋掉落算法和數(shù)據(jù)結(jié)構(gòu)解析第一章算法簡(jiǎn)介作為程序員，大家對(duì)“算法”這個(gè)詞一定非常熟悉。不論是理論學(xué)習(xí)、求職面試，還是項(xiàng)目開(kāi)發(fā)，算法往往都是程序員關(guān)注的重點(diǎn)之一。那算法到底是什么？想要系統(tǒng)地學(xué)習(xí)算法，又應(yīng)該從哪里入手呢？本課程就將為大家打開(kāi)算法學(xué)習(xí)的大門(mén)。首先，我們應(yīng)該了解算法的基本概念。1.1算法的基本概念1.1.1什么是算法算法（Algorithm），就是“計(jì)算方法”，指解決一個(gè)問(wèn)題具體的步驟和方法。對(duì)于計(jì)算機(jī)而言，就是一系列解決問(wèn)題的清晰指令。也就是說(shuō)，對(duì)于一個(gè)問(wèn)題，我們可以通過(guò)算法來(lái)描述解決的策略和步驟；對(duì)于規(guī)范的輸入，按照算法描述的步驟，就可以在有限時(shí)間內(nèi)得到對(duì)應(yīng)的輸出。1.1.2為什么要學(xué)習(xí)算法首先，算法是計(jì)算機(jī)程序的核心。在一個(gè)計(jì)算機(jī)程序中，有兩個(gè)非常重要的部分：數(shù)據(jù)結(jié)構(gòu)和算法。數(shù)據(jù)結(jié)構(gòu)決定了程序中數(shù)據(jù)組織和存儲(chǔ)的形式，而算法決定了程序的功能和效率。算法在具體應(yīng)用時(shí)，與數(shù)據(jù)結(jié)構(gòu)密不可分，是一個(gè)程序的靈魂。其次，算法是程序員的核心競(jìng)爭(zhēng)力。算法是解決問(wèn)題的方法和步驟，所以掌握了算法，就可以擁有更強(qiáng)的解決問(wèn)題的能力。對(duì)于一個(gè)程序員而言，這往往比學(xué)會(huì)用一個(gè)框架、一個(gè)工具更加重要。再次，算法是IT大廠面試的必考環(huán)節(jié)。大家可能知道，在IT特別是互聯(lián)網(wǎng)公司的面試過(guò)程中，數(shù)據(jù)結(jié)構(gòu)和算法是非常重要的一部分，為什么大廠都青睞于考察算法呢？總結(jié)起來(lái)，考察的原因以下幾點(diǎn)：看一個(gè)程序員的技術(shù)功底是否扎實(shí)，考算法是最好的方式；看一個(gè)程序員的學(xué)習(xí)能力，和成長(zhǎng)潛力，最好就是看他的算法能力；算法能力強(qiáng)，可以在面對(duì)新問(wèn)題時(shí)，有更強(qiáng)的分析并解決問(wèn)題的能力；算法能力，是設(shè)計(jì)一個(gè)高性能系統(tǒng)、性能優(yōu)化的必備基礎(chǔ)。所以，算法是程序員繞不過(guò)去的必修課，也是走向架構(gòu)師的必經(jīng)之路。1.1.3怎樣學(xué)習(xí)算法首先，在學(xué)習(xí)算法之前，應(yīng)該至少熟練掌握一門(mén)編程語(yǔ)言。本課程中的代碼實(shí)現(xiàn)，都會(huì)以java為例來(lái)講解。其次，算法和數(shù)據(jù)結(jié)構(gòu)密不可分，在系統(tǒng)學(xué)習(xí)算法之前，最好能夠?qū)镜臄?shù)據(jù)結(jié)構(gòu)，數(shù)組、鏈表、哈希表、棧、隊(duì)列、樹(shù)都有充分的了解。在后續(xù)的課程中，我們會(huì)以算法講解為主、穿插復(fù)習(xí)一些數(shù)據(jù)結(jié)構(gòu)的基本知識(shí)。當(dāng)然，算法本身是解題方法，有些也是不依賴(lài)于數(shù)據(jù)結(jié)構(gòu)的，所以即使沒(méi)有系統(tǒng)學(xué)過(guò)數(shù)據(jù)結(jié)構(gòu)，同樣可以開(kāi)始算法的學(xué)習(xí)。最后，算法學(xué)習(xí)的捷徑，就是用算法去解決大量的具體問(wèn)題，也就是通常所說(shuō)的“刷題”。如果目的在于通過(guò)大廠面試，那這一步更是必不可少的準(zhǔn)備。最經(jīng)典的刷題網(wǎng)站，毫無(wú)疑問(wèn)就是leetcode（力扣）。所以我們接下來(lái)的學(xué)習(xí)過(guò)程中，就會(huì)以leetcode的原題為例，分門(mén)別類(lèi)進(jìn)行算法的講解，在具體解題的過(guò)程中鞏固深化算法的學(xué)習(xí)。1.2算法的特征一個(gè)算法應(yīng)該具有以下五個(gè)重要的特征：有窮性（Finiteness）算法的有窮性，是指算法必須能在執(zhí)行有限個(gè)步驟之后終止。確切性（Definiteness）算法的每一步驟必須有確切的定義。輸入項(xiàng)（Input）一個(gè)算法有0個(gè)或多個(gè)輸入，以刻畫(huà)運(yùn)算對(duì)象的初始情況。所謂0個(gè)輸入，是指算法本身定出了初始條件。輸出項(xiàng)（Output）一個(gè)算法有一個(gè)或多個(gè)輸出，以反映對(duì)輸入數(shù)據(jù)加工后的結(jié)果?？尚行裕‥ffectiveness）算法中執(zhí)行的任何計(jì)算步驟都是可以被分解為基本的可執(zhí)行的操作步驟，即每個(gè)計(jì)算步驟都可以在有限時(shí)間內(nèi)完成（也稱(chēng)之為有效性）。1.3算法復(fù)雜度基于算法的有窮性，我們可以知道算法運(yùn)行消耗的時(shí)間不能是無(wú)限的。而對(duì)于一個(gè)問(wèn)題的處理，可能有多個(gè)不同的算法，它們消耗的時(shí)間一般是不同的；運(yùn)行過(guò)程中占用的空間資源也是不同的。這就涉及到對(duì)算法的性能考察。主要有兩方面：時(shí)間和空間。在計(jì)算機(jī)算法理論中，用時(shí)間復(fù)雜度和空間復(fù)雜度來(lái)分別從這兩方面衡量算法的性能。1.3.1時(shí)間復(fù)雜度（TimeComplexity）算法的時(shí)間復(fù)雜度，是指執(zhí)行算法所需要的計(jì)算工作量。一般來(lái)說(shuō)，計(jì)算機(jī)算法是問(wèn)題規(guī)模n的函數(shù)f(n)，算法的時(shí)間復(fù)雜度也因此記做：T(n)=Ο(f(n))。問(wèn)題的規(guī)模n越大，算法執(zhí)行的時(shí)間的增長(zhǎng)率與f(n)的增長(zhǎng)率正相關(guān)，稱(chēng)作漸進(jìn)時(shí)間復(fù)雜度（AsymptoticTimeComplexity）。1.3.2空間復(fù)雜度算法的空間復(fù)雜度，是指算法需要消耗的內(nèi)存空間。有時(shí)候做遞歸調(diào)用，還需要考慮調(diào)用棧所占用的空間。其計(jì)算和表示方法與時(shí)間復(fù)雜度類(lèi)似，一般都用復(fù)雜度的漸近性來(lái)表示。同時(shí)間復(fù)雜度相比，空間復(fù)雜度的分析要簡(jiǎn)單得多。所以，我們一般對(duì)程序復(fù)雜度的分析，重點(diǎn)都會(huì)放在時(shí)間復(fù)雜度上。1.3.3時(shí)間復(fù)雜度的計(jì)算要想衡量代碼的“工作量”，我們需要將每一行代碼，拆解成計(jì)算機(jī)能執(zhí)行一條條“基本指令”。這樣代碼的執(zhí)行時(shí)間，就可以用“基本指令”的數(shù)量來(lái)表示了。真實(shí)的計(jì)算機(jī)系統(tǒng)里，基本指令包括：算術(shù)指令（加減乘除、取余、向上向下取整）、數(shù)據(jù)移動(dòng)指令（裝載、存儲(chǔ)、賦值）、控制指令（條件或無(wú)條件跳轉(zhuǎn)，子程序調(diào)用和返回）。我們來(lái)看一些具體的代碼，分析一下它們的時(shí)間復(fù)雜度：inta=1；簡(jiǎn)單賦值操作，運(yùn)行時(shí)間1（1個(gè)單位）if(a>1){}簡(jiǎn)單判斷操作、條件跳轉(zhuǎn)，運(yùn)行時(shí)間1for(inti=0;i<N;i++){System.out.println(i);}有循環(huán)，運(yùn)行時(shí)間1（i賦初值）+N+1（判斷）+N（打?。?N（i自增）=3N+21.3.4復(fù)雜度的大O表示法比起代碼具體運(yùn)行的時(shí)間，我們更關(guān)心的是，當(dāng)它的輸入規(guī)模增長(zhǎng)的時(shí)候，它的執(zhí)行時(shí)間我們是否還能夠接受。不同的算法，運(yùn)行時(shí)間隨著輸入規(guī)模n的增長(zhǎng)速度是不同的。我們可以把代碼執(zhí)行時(shí)間，表示成輸入規(guī)模n的函數(shù)T(n)。在算法分析中，一般用大O符號(hào)來(lái)表示函數(shù)的漸進(jìn)上界。對(duì)于給定的函數(shù)g(n)，我們用O(g(n))來(lái)表示以下函數(shù)的集合：O(g(n))={f(n):存在正常量c和n0，使對(duì)所有n≥n0，有0≤f(n)≤cg(n)}這表示，當(dāng)數(shù)據(jù)量達(dá)到一定程度時(shí)，g(n)的增長(zhǎng)速度不會(huì)超過(guò)O(g(n))限定的范圍。也就是說(shuō)，大O表示了函數(shù)的“階數(shù)”，階數(shù)越高，增長(zhǎng)趨勢(shì)越大，后期增長(zhǎng)越快。下圖畫(huà)出了常見(jiàn)的算法復(fù)雜度：1.4算法的分類(lèi)可以用兩種不同的原則，來(lái)對(duì)算法做一個(gè)分類(lèi)整理：按照應(yīng)用的目的來(lái)劃分搜索算法、排序算法、字符串算法、圖算法、最優(yōu)化算法、數(shù)學(xué)（數(shù)論）算法按照具體實(shí)現(xiàn)的策略劃分暴力法、增量法、分治法、貪心、動(dòng)態(tài)規(guī)劃、回溯、分支限界法1.5經(jīng)典算法在實(shí)際應(yīng)用中，有一些經(jīng)典算法和策略，都可以作為解決問(wèn)題的思路：二分查找快速排序、歸并排序KMP算法快慢指針（雙指針?lè)ǎ┢绽罚≒rim）和克魯斯卡爾（Kruskal）算法迪克斯特拉（Dijkstra）算法其它優(yōu)化算法：模擬退火、蟻群、遺傳算法接下來(lái)，我們就不同的數(shù)據(jù)結(jié)構(gòu)和算法策略進(jìn)行分類(lèi)，用不同的算法在各章節(jié)中解決某一類(lèi)問(wèn)題。

第二章數(shù)組問(wèn)題講解在程序設(shè)計(jì)中，為了處理方便，常常需要把具有相同類(lèi)型的若干元素按有序的形式組織起來(lái)，這種形式就是數(shù)組（Array）。數(shù)組是程序中最常見(jiàn)、也是最基本的數(shù)據(jù)結(jié)構(gòu)。在很多算法問(wèn)題中，都少不了數(shù)組的處理和轉(zhuǎn)換。對(duì)數(shù)組進(jìn)行處理需要注意以下特點(diǎn)：首先，數(shù)組會(huì)利用索引來(lái)記錄每個(gè)元素在數(shù)組中的位置，且在大多數(shù)編程語(yǔ)言中，索引是從0算起的。我們可以根據(jù)數(shù)組中的索引，快速訪問(wèn)數(shù)組中的元素。事實(shí)上，這里的索引其實(shí)就是內(nèi)存地址。其次，作為線性表的實(shí)現(xiàn)方式之一，數(shù)組中的元素在內(nèi)存中是連續(xù)存儲(chǔ)的，且每個(gè)元素占用相同大小的內(nèi)存。接下來(lái)，我們就以LeetCode上一些數(shù)組相關(guān)的題目為例，來(lái)學(xué)習(xí)解決數(shù)組問(wèn)題的算法。2.1兩數(shù)之和（#1）2.2.1題目說(shuō)明給定一個(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)閚ums[0]+nums[1]=2+7=9所以返回[0,1]2.2.2方法一：暴力法看到一道算法題，首先考慮暴力解法，再進(jìn)行優(yōu)化。暴力法其實(shí)非常簡(jiǎn)單：把所有數(shù)、兩兩組合在一起，計(jì)算它們的和，如果是target，就輸出。我們可以在代碼中實(shí)現(xiàn)一下：publicint[]twoSum(int[]nums,inttarget){for(inti=0;i<nums.length;i++){for(intj=i+1;j<nums.length;j++){if(nums[i]+nums[j]==target)returnnewint[]{i,j};}}thrownewIllegalArgumentException("Notwosumsolution");}復(fù)雜度分析時(shí)間復(fù)雜度：O(n^2)，對(duì)于每個(gè)元素，我們?cè)噲D通過(guò)遍歷數(shù)組的其余部分來(lái)尋找它所對(duì)應(yīng)的目標(biāo)元素，這將耗費(fèi)

O(n)。空間復(fù)雜度：O(1)。2.2.3方法二：兩遍哈希表為了對(duì)運(yùn)行時(shí)間復(fù)雜度進(jìn)行優(yōu)化，我們需要一種更有效的方法來(lái)檢查數(shù)組中是否存在目標(biāo)元素。如果存在，我們需要找出它的索引。這可以使用哈希表來(lái)實(shí)現(xiàn)。具體實(shí)現(xiàn)方法，最簡(jiǎn)單就是使用兩次迭代。在第一次迭代中，我們將每個(gè)元素的值和它的索引添加到表中；然后，在第二次迭代中，我們將檢查每個(gè)元素所對(duì)應(yīng)的目標(biāo)元素

(target-nums[i])

是否存在于表中。代碼如下：publicint[]twoSum(intnums[],inttarget){Map<Integer,Integer>map=newHashMap<>();//遍歷數(shù)組，全部保存到hashmap中for(inti=0;i<nums.length;i++){map.put(nums[i],i);}//遍歷數(shù)組，挨個(gè)查找對(duì)應(yīng)的“那個(gè)數(shù)”在不在map中for(inti=0;i<nums.length;i++){intthatNum=target-nums[i];if(map.containsKey(thatNum)&&map.get(thatNum)!=i)returnnewint[]{i,map.get(thatNum)};}thrownewIllegalArgumentException("Notwosumsolution");

}復(fù)雜度分析時(shí)間復(fù)雜度：O(N)，我們把包含有

N

個(gè)元素的列表遍歷兩次。由于哈希表將查找時(shí)間縮短到

O(1)，所以時(shí)間復(fù)雜度為

O(N)?？臻g復(fù)雜度：O(N)，所需的額外空間取決于哈希表中存儲(chǔ)的元素?cái)?shù)量，該表中存儲(chǔ)了

N

個(gè)元素。2.2.4方法三：一遍哈希表在上述算法中，我們對(duì)哈希表進(jìn)行了兩次掃描，這其實(shí)是不必要的。在進(jìn)行迭代并將元素插入到表中的同時(shí)，我們可以直接檢查表中是否已經(jīng)存在當(dāng)前元素所對(duì)應(yīng)的目標(biāo)元素。如果它存在，那我們已經(jīng)找到了對(duì)應(yīng)解，并立即將其返回。這樣，只需要掃描一次哈希表，就可以完成算法了。代碼如下：publicint[]twoSum(intnums[],inttarget){Map<Integer,Integer>map=newHashMap<>();for(inti=0;i<nums.length;i++){intthatNum=target-nums[i];if(map.containsKey(thatNum)&&map.get(thatNum)!=i)returnnewint[]{map.get(thatNum),i};map.put(nums[i],i);}thrownewIllegalArgumentException("Notwosumsolution");

}復(fù)雜度分析時(shí)間復(fù)雜度：O(N)，我們只遍歷了包含有

N

個(gè)元素的列表一次。在表中進(jìn)行的每次查找只花費(fèi)

O(1)

的時(shí)間。其實(shí)這個(gè)過(guò)程中，我們也借鑒了動(dòng)態(tài)規(guī)劃的思想、把子問(wèn)題解保存起來(lái)，后面用到就直接查詢(xún)?？臻g復(fù)雜度：O(N)，所需的額外空間取決于哈希表中存儲(chǔ)的元素?cái)?shù)量，該表最多需要存儲(chǔ)

N

個(gè)元素。2.2三數(shù)之和（#15）2.2.1題目說(shuō)明給定一個(gè)包含n個(gè)整數(shù)的數(shù)組

nums，判斷

nums

中是否存在三個(gè)元素a，b，c，使得

a+b+c=0？找出所有滿(mǎn)足條件且不重復(fù)的三元組。注意：答案中不可以包含重復(fù)的三元組。示例:給定數(shù)組nums=[-1,0,1,2,-1,-4]，滿(mǎn)足要求的三元組集合為：[[-1,0,1],[-1,-1,2]]2.2.2分析這個(gè)問(wèn)題比起兩數(shù)之和來(lái)，顯然要復(fù)雜了一些，而且由于結(jié)果可能有多種情況，還要考慮去重，整體難度提升了不少。最后的返回，就不再是一個(gè)簡(jiǎn)單的數(shù)組了，而是“數(shù)組的數(shù)組”，每一組解都是一個(gè)數(shù)組，最終有多組解都要返回。2.2.3方法一：暴力法最簡(jiǎn)單的辦法，當(dāng)然還是暴力法?；舅悸肥?，每個(gè)人都先去找到另一個(gè)人，然后再一起逐個(gè)去找第三個(gè)人。很容易想到，實(shí)現(xiàn)起來(lái)就是三重循環(huán)：這個(gè)時(shí)間復(fù)雜度是O(n^3)。代碼如下：publicList<List<Integer>>threeSum(int[]nums){intn=nums.length;List<List<Integer>>resultList=newArrayList<>();//三重循環(huán)，遍歷所有的三數(shù)組合for(inti=0;i<n-2;i++){for(intj=i+1;j<n-1;j++){for(intk=j+1;k<n;k++){if(nums[i]+nums[j]+nums[k]==0){resultList.add(Arrays.asList(nums[i],nums[j],nums[k]));}}}}returnresultList;}運(yùn)行一下，我們會(huì)發(fā)現(xiàn)，這個(gè)結(jié)果其實(shí)是不正確的沒(méi)有去重，同樣的三元組在結(jié)果中無(wú)法排除。比如-1，0，1會(huì)出現(xiàn)兩次。而且時(shí)間復(fù)雜度非常高，是N^3。所以接下來(lái)，我們就要做一些改進(jìn)，試圖降低時(shí)間復(fù)雜度，而且解決去重問(wèn)題。2.2.4暴力法的改進(jìn)：結(jié)果去重要做去重，自然首先想到的，就是把結(jié)果保存到一張hash表里。仿照兩數(shù)之和，直接存到HashMap里查找，代碼如下：publicList<List<Integer>>threeSum(int[]nums){intn=nums.length;List<List<Integer>>result=newArrayList<>();Map<Integer,List<Integer>>hashMap=newHashMap<>();

//遍歷數(shù)組，尋找每個(gè)元素的thatNum

for(inti=0;i<n;i++){

intthatNum=0-nums[i];

if(hashMap.containsKey(thatNum)){

List<Integer>tempList=newArrayList<>(hashMap.get(thatNum));

tempList.add(nums[i]);

result.add(tempList);

continue;

}

for(intj=0;j<i;j++){

intnewKey=nums[i]+nums[j];

if(!hashMap.containsKey(newKey)){

List<Integer>tempList=newArrayList<>();

tempList.add(nums[j]);

tempList.add(nums[i]);

hashMap.put(newKey,tempList);

}

}

}

returnresult;

}時(shí)間復(fù)雜度降為N^2，空間復(fù)雜度O(N)。但是，我們加一個(gè)輸入[0,0,0,0]，會(huì)發(fā)現(xiàn)結(jié)果不正確。因?yàn)楸M管通過(guò)HashMap存儲(chǔ)可以去掉相同二元組的計(jì)算結(jié)果的值，但沒(méi)有去掉重復(fù)的輸出（三元組）。這就導(dǎo)致，0對(duì)應(yīng)在HashMap中有一個(gè)值（0，List（0，0）），第三個(gè)0來(lái)了會(huì)輸出一次，第四個(gè)0來(lái)了又會(huì)輸出一次。如果希望解決這個(gè)問(wèn)題，那就需要繼續(xù)加入其它的判斷來(lái)做去重，整個(gè)代碼復(fù)雜度會(huì)變得更高。2.2.5方法二：雙指針?lè)ū┝Ψㄋ阉鲿r(shí)間復(fù)雜度為O(N^3)，要進(jìn)行優(yōu)化，可通過(guò)雙指針動(dòng)態(tài)消去無(wú)效解來(lái)提高效率。雙指針的思路，又分為左右指針和快慢指針兩種。我們這里用的是左右指針。左右指針，其實(shí)借鑒的就是分治的思想，簡(jiǎn)單來(lái)說(shuō)，就是在數(shù)組頭尾各放置一個(gè)指針，先讓頭部的指針（左指針）右移，移不動(dòng)的時(shí)候，再讓尾部的指針（右指針）左移：最終兩個(gè)指針相遇，那么搜索就結(jié)束了。（1）雙指針?lè)ㄤ亯|：先將給定nums排序，復(fù)雜度為O(NlogN)。首先，我們可以想到，數(shù)字求和，其實(shí)跟每個(gè)數(shù)的大小是有關(guān)系的，如果能先將數(shù)組排序，那后面肯定會(huì)容易很多。之前我們搜索數(shù)組，時(shí)間復(fù)雜度至少都為O(N^2)，而如果用快排或者歸并，排序的復(fù)雜度，是O(NlogN)，最多也是O(N^2)。所以增加一步排序，不會(huì)導(dǎo)致整體時(shí)間復(fù)雜度上升。下面我們通過(guò)圖解，來(lái)看一下具體的操作過(guò)程。（2）初始狀態(tài)，定義左右指針L和R，并以指針i遍歷數(shù)組元素。固定3個(gè)指針中最左（最?。?shù)字的指針i，雙指針L，R分設(shè)在數(shù)組索引(i,len(nums))兩端，所以初始值，i=0；L=i+1；R=nums.length-1通過(guò)L、R雙指針交替向中間移動(dòng)，記錄對(duì)于每個(gè)固定指針i的所有滿(mǎn)足nums[i]+nums[L]+nums[R]==0的L,R組合。兩個(gè)基本原則：當(dāng)nums[i]>0時(shí)直接break跳出：因?yàn)閚ums[R]>=nums[L]>=nums[i]>0，即3個(gè)數(shù)字都大于0，在此固定指針i之后不可能再找到結(jié)果了。當(dāng)i>0且nums[i]==nums[i-1]時(shí)，即遇到重復(fù)元素時(shí)，跳過(guò)此元素nums[i]：因?yàn)橐呀?jīng)將nums[i-1]的所有組合加入到結(jié)果中，本次雙指針?biāo)阉髦粫?huì)得到重復(fù)組合。（3）固定i，判斷sum，然后移動(dòng)左右指針L和R。L，R分設(shè)在數(shù)組索引(i,len(nums))兩端，當(dāng)L<R時(shí)循環(huán)計(jì)算當(dāng)前三數(shù)之和：sum=nums[i]+nums[L]+nums[R]并按照以下規(guī)則執(zhí)行雙指針移動(dòng)：當(dāng)sum<0時(shí)，L++并跳過(guò)所有重復(fù)的nums[L]；由于sum<0，L一直右移，直到跟R重合。如果依然沒(méi)有結(jié)果，那么i++，換下一個(gè)數(shù)考慮。換下一個(gè)數(shù)，i++，繼續(xù)移動(dòng)雙指針：初始同樣還是L=i+1，R=nums.length-1。同樣，繼續(xù)判斷sum。找到一組解之后，繼續(xù)移動(dòng)L和R，判斷sum，如果小于0就右移L，如果大于0就左移R：找到一組解[-1,-1,2]，保存，并繼續(xù)右移L。判斷sum，如果這時(shí)sum=-1+0+2>0，（R還沒(méi)變，還是5），那么就讓L停下，開(kāi)始左移R。一直移動(dòng)，又找到一組解如果又找到sum=0的一組解，把當(dāng)前的[-1,0,1]也保存到結(jié)果數(shù)組。繼續(xù)右移L。如果L和R相遇或者L>R，代表當(dāng)前i已經(jīng)排查完畢，i++；如果i指向的數(shù)跟i-1一樣，那么直接繼續(xù)i++，考察下一個(gè)數(shù)；這時(shí)i=3，類(lèi)似地，當(dāng)sum>0時(shí)，R左移R-=1，并跳過(guò)所有重復(fù)的nums[R]；L和R相遇，結(jié)束當(dāng)前查找，i++。當(dāng)nums[i]>0時(shí)直接break跳出：過(guò)程結(jié)束。所以，最終的結(jié)果，就是[-1,-1,2],[-1,0,1]。代碼如下：publicList<List<Integer>>threeSum(int[]nums){intn=nums.length;List<List<Integer>>result=newArrayList<>();//先對(duì)數(shù)組進(jìn)行排序

Arrays.sort(nums);

for(inti=0;i<n;i++){

if(nums[i]>0)

break;

if(i>0&&nums[i]==nums[i-1])

continue;

//定義左右指針（索引位置）

intlp=i+1;

intrp=n-1;

//只要左右不重疊，就繼續(xù)移動(dòng)指針

while(lp<rp){

intsum=nums[i]+nums[lp]+nums[rp];

if(sum==0){

result.add(Arrays.asList(nums[i],nums[lp],nums[rp]));

lp++;

rp--;

while(lp<rp&&nums[lp]==nums[lp-1])

lp++;

while(lp<rp&&nums[rp]==nums[rp+1])

rp--;

}

elseif(sum<0)

lp++;

else

rp--;

}

}

returnresult;

}復(fù)雜度分析：時(shí)間復(fù)雜度O(N^2)：其中固定指針k循環(huán)復(fù)雜度O(N)，雙指針i，j復(fù)雜度O(N)。比暴力法的O(n^3)，顯然有了很大的改善?？臻g復(fù)雜度O(1)：指針使用常數(shù)大小的額外空間。盡管時(shí)間復(fù)雜度依然為O(n^2)，但是過(guò)程中避免了復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，空間復(fù)雜度僅為常數(shù)級(jí)O(1)，可以說(shuō)，雙指針?lè)ㄊ且环N很巧妙、很優(yōu)雅的算法設(shè)計(jì)。2.3下一個(gè)排列（#31）2.3.1題目說(shuō)明實(shí)現(xiàn)獲取下一個(gè)排列的函數(shù)，算法需要將給定數(shù)字序列重新排列成字典序中下一個(gè)更大的排列。如果不存在下一個(gè)更大的排列，則將數(shù)字重新排列成最小的排列（即升序排列）。必須原地修改，只允許使用額外常數(shù)空間。以下是一些例子，輸入位于左側(cè)列，其相應(yīng)輸出位于右側(cè)列。1,2,3→1,3,23,2,1→1,2,31,1,5→1,5,12.3.2方法一：暴力法最簡(jiǎn)單的想法就是暴力枚舉，我們找出由給定數(shù)組的元素形成的列表的每個(gè)可能的排列，并找出比給定的排列更大的排列。但是這個(gè)方法要求我們找出所有可能的排列，這需要很長(zhǎng)時(shí)間，實(shí)施起來(lái)也很復(fù)雜。因此，這種算法不能滿(mǎn)足要求。我們跳過(guò)它的實(shí)現(xiàn)，直接采用正確的方法。復(fù)雜度分析時(shí)間復(fù)雜度：O(n!)，可能的排列總計(jì)有n!個(gè)?？臻g復(fù)雜度：O(n)，因?yàn)閿?shù)組將用于存儲(chǔ)排列。2.3.3方法二：一遍掃描首先，我們觀察到對(duì)于任何給定序列的降序排列，就不會(huì)有下一個(gè)更大的排列。例如，以下數(shù)組不可能有下一個(gè)排列：[9,5,4,3,1]這時(shí)應(yīng)該直接返回升序排列。所以對(duì)于一般的情況，如果有一個(gè)“升序子序列”，那么就一定可以找到它的下一個(gè)排列。具體來(lái)說(shuō)，需要從右邊找到第一對(duì)兩個(gè)連續(xù)的數(shù)字a[i]和a[i-1]，它們滿(mǎn)足a[i]>a[i-1]。所以一個(gè)思路是，找到最后一個(gè)的“正序”排列的子序列，把它改成下一個(gè)排列就行了。不過(guò)具體操作會(huì)發(fā)現(xiàn)，如果正序子序列后沒(méi)數(shù)了，那么子序列的“下一個(gè)”一定就是整個(gè)序列的“下一個(gè)”，這樣做沒(méi)問(wèn)題；但如果后面還有逆序排列的數(shù)，這樣就不對(duì)了。比如[1,3,8,7,6,2]最后的正序子序列是[1,3,8]，但顯然不能直接換成[1,8,3]就完事了；而是應(yīng)該考慮把3換成后面比3大、但比8小的數(shù)，而且要選最小的那個(gè)（6）。接下來(lái)，還要讓6之后的所有數(shù)，做一個(gè)升序排列，得到結(jié)果：[1,6,2,3,7,8]代碼實(shí)現(xiàn)如下：publicvoidnextPermutation(int[]nums){

intk=nums.length-2;

while(k>=0&&nums[k]>=nums[k+1])

k--;

//如果全部降序，以最小序列輸出

if(k<0){

Arrays.sort(nums);

return;

}

inti=k+2;

while(i<nums.length&&nums[i]>nums[k])

i++;

//交換nums[k]和找到的nums[i-1]

inttemp=nums[k];

nums[k]=nums[i-1];

nums[i-1]=temp;

//k以后剩余的部分反轉(zhuǎn)成升序

intstart=k+1,end=nums.length-1;

while(start<end){

intreTemp=nums[start];

nums[start]=nums[end];

nums[end]=reTemp;

start++;

end--;

}

}復(fù)雜度分析時(shí)間復(fù)雜度：O(N)，其中NN為給定序列的長(zhǎng)度。我們至多只需要掃描兩次序列，以及進(jìn)行一次反轉(zhuǎn)操作?？臻g復(fù)雜度：O(1)，只需要常數(shù)的空間存放若干變量。2.4旋轉(zhuǎn)圖像（#48）2.4.1題目說(shuō)明給定一個(gè)n

×

n的二維矩陣表示一個(gè)圖像。將圖像順時(shí)針旋轉(zhuǎn)90度。說(shuō)明：你必須在原地旋轉(zhuǎn)圖像，這意味著你需要直接修改輸入的二維矩陣。請(qǐng)不要使用另一個(gè)矩陣來(lái)旋轉(zhuǎn)圖像。示例1:給定matrix=[[1,2,3],[4,5,6],[7,8,9]],原地旋轉(zhuǎn)輸入矩陣，使其變?yōu)?[[7,4,1],[8,5,2],[9,6,3]]示例2:給定matrix=[[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]],原地旋轉(zhuǎn)輸入矩陣，使其變?yōu)?[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]2.4.2分析旋轉(zhuǎn)圖像，這個(gè)應(yīng)用在圖片處理的過(guò)程中，非常常見(jiàn)。我們知道對(duì)于計(jì)算機(jī)而言，圖像，其實(shí)就是一組像素點(diǎn)的集合（所謂點(diǎn)陣），所以圖像旋轉(zhuǎn)的問(wèn)題，本質(zhì)上就是一個(gè)二維數(shù)組的旋轉(zhuǎn)問(wèn)題。2.4.3方法一：數(shù)學(xué)方法（轉(zhuǎn)置再翻轉(zhuǎn)）我們可以利用矩陣的特性。所謂順時(shí)針旋轉(zhuǎn)，其實(shí)就是先轉(zhuǎn)置矩陣，然后翻轉(zhuǎn)每一行。代碼如下：publicvoidrotate(int[][]matrix){

intn=matrix.length;

//轉(zhuǎn)置矩陣

for(inti=0;i<n;i++)

for(intj=i;j<n;j++){

inttmp=matrix[i][j];

matrix[i][j]=matrix[j][i];

matrix[j][i]=tmp;

}

//翻轉(zhuǎn)行

for(inti=0;i<n;i++){

for(intj=0;j<n/2;j++){

inttmp=matrix[i][j];

matrix[i][j]=matrix[i][n-j-1];

matrix[i][n-j-1]=tmp;

}

}

}復(fù)雜度分析時(shí)間復(fù)雜度：O(N^2)這個(gè)簡(jiǎn)單的方法已經(jīng)能達(dá)到最優(yōu)的時(shí)間復(fù)雜度O(N^2)，因?yàn)榧热皇切D(zhuǎn)，那么每個(gè)點(diǎn)都應(yīng)該遍歷到，N^2的復(fù)雜度不可避免?？臻g復(fù)雜度：O(1)。旋轉(zhuǎn)操作是原地完成的，只耗費(fèi)常數(shù)空間。2.4.4方法二：分治（分為四部分旋轉(zhuǎn)）方法1使用了兩次矩陣操作，能不能只使用一次操作的方法完成旋轉(zhuǎn)呢？為了實(shí)現(xiàn)這一點(diǎn)，我們來(lái)研究每個(gè)元素在旋轉(zhuǎn)的過(guò)程中如何移動(dòng)。這提供給我們了一個(gè)思路，可以將給定的矩陣分成四個(gè)矩形并且將原問(wèn)題劃歸為旋轉(zhuǎn)這些矩形的問(wèn)題。這其實(shí)就是分治的思想。具體解法也很直接，可以在每一個(gè)矩形中遍歷元素，并且在長(zhǎng)度為4的臨時(shí)列表中移動(dòng)它們。代碼如下：publicvoidrotate(int[][]matrix){intn=matrix.length;for(inti=0;i<n/2+n%2;i++){for(intj=0;j<n/2;j++){int[]tmp=newint[4];introw=i;intcol=j;for(intk=0;k<4;k++){tmp[k]=matrix[row][col];//定位下一個(gè)數(shù)intx=row;row=col;col=n-1-x;}for(intk=0;k<4;k++){matrix[row][col]=tmp[(k+3)%4];intx=row;row=col;col=n-1-x;}}}

}復(fù)雜度分析時(shí)間復(fù)雜度：O(N^2)是兩重循環(huán)的復(fù)雜度?？臻g復(fù)雜度：O(1)由于我們?cè)谝淮窝h(huán)中的操作是“就地”完成的，并且我們只用了長(zhǎng)度為4的臨時(shí)列表做輔助。2.4.5方法三：分治法改進(jìn)（單次循環(huán)內(nèi)完成旋轉(zhuǎn)）大家可能也發(fā)現(xiàn)了，我們其實(shí)沒(méi)有必要分成4個(gè)矩陣來(lái)旋轉(zhuǎn)。這四個(gè)矩陣的對(duì)應(yīng)關(guān)系，其實(shí)是一目了然的，我們完全可以在一次循環(huán)內(nèi)，把所有元素都旋轉(zhuǎn)到位。因?yàn)樾D(zhuǎn)的時(shí)候，是上下、左右分別對(duì)稱(chēng)的，所以我們遍歷元素的時(shí)候，只要遍歷一半行、一半列就可以了（1/4元素）。代碼如下：publicvoidrotate(int[][]matrix){intn=matrix.length;//不區(qū)分子矩陣，直接遍歷每一個(gè)元素for(inti=0;i<(n+1)/2;i++){for(intj=0;j<n/2;j++){inttemp=matrix[i][j];matrix[i][j]=matrix[n-j-1][i];matrix[n-j-1][i]=matrix[n-i-1][n-j-1];matrix[n-i-1][n-j-1]=matrix[j][n-i-1];matrix[j][n-i-1]=temp;}}

}復(fù)雜度分析時(shí)間復(fù)雜度：O(N^2)，是兩重循環(huán)的復(fù)雜度?？臻g復(fù)雜度：O(1)。我們?cè)谝淮窝h(huán)中的操作是“就地”完成的。

第三章二分查找相關(guān)問(wèn)題講解3.1二分查找二分查找也稱(chēng)折半查找（BinarySearch），它是一種效率較高的查找方法，前提是數(shù)據(jù)結(jié)構(gòu)必須先排好序，可以在對(duì)數(shù)時(shí)間復(fù)雜度內(nèi)完成查找。二分查找事實(shí)上采用的就是一種分治策略，它充分利用了元素間的次序關(guān)系，可在最壞的情況下用O(logn)完成搜索任務(wù)。它的基本思想是：假設(shè)數(shù)組元素呈升序排列，將n個(gè)元素分成個(gè)數(shù)大致相同的兩半，取a[n/2]與欲查找的x作比較，如果x=a[n/2]則找到x，算法終止；如果x<a[n/2]，則我們只要在數(shù)組a的左半部繼續(xù)搜索x；如果x>a[n/2]，則我們只要在數(shù)組a的右半部繼續(xù)搜索x。二分查找問(wèn)題也是面試中經(jīng)?？嫉降膯?wèn)題，雖然它的思想很簡(jiǎn)單，但寫(xiě)好二分查找算法并不是一件容易的事情。接下來(lái)，我們首先用代碼實(shí)現(xiàn)一個(gè)對(duì)int數(shù)組的二分查找。publicclassBinarySearch{

publicstaticintbinarySearch(int[]a,intkey){

intlow=0;

inthigh=a.length-1;

if(key<a[low]||key>a[high])

return-1;

while(low<=high){

intmid=(low+high)/2;

if(a[mid]<key)

low=mid+1;

elseif(a[mid]>key)

high=mid-1;

else

returnmid;//查找成功

}

//未能找到

return-1;

}

}當(dāng)然，我們也可以用遞歸的方式實(shí)現(xiàn)：publicstaticintbinarySearch(int[]a,intkey,intfromIndex,inttoIndex){

if(key<a[fromIndex]||key>a[toIndex]||fromIndex>toIndex)

return-1;

intmid=(fromIndex+toIndex)/2;

if(a[mid]<key)

returnbinarySearch(a,key,mid+1,toIndex);

elseif(a[mid]>key)

returnbinarySearch(a,key,fromIndex,mid-1);

else

returnmid;

}我們總結(jié)一下二分查找：優(yōu)點(diǎn)是比較次數(shù)少，查找速度快，平均性能好；缺點(diǎn)是要求待查表為有序表，且插入刪除困難。因此，二分查找方法適用于不經(jīng)常變動(dòng)而查找頻繁的有序列表。使用條件：查找序列是順序結(jié)構(gòu)，有序。3.2搜索二維矩陣（#74）3.2.1題目說(shuō)明編寫(xiě)一個(gè)高效的算法來(lái)判斷

mxn

矩陣中，是否存在一個(gè)目標(biāo)值。該矩陣具有如下特性：每行中的整數(shù)從左到右按升序排列。每行的第一個(gè)整數(shù)大于前一行的最后一個(gè)整數(shù)。示例1：輸入：matrix=[[1,3,5,7],[10,11,16,20],[23,30,34,50]],target=3輸出：true示例2：輸入：matrix=[[1,3,5,7],[10,11,16,20],[23,30,34,50]],target=13輸出：false示例3：輸入：matrix=[],target=0輸出：false提示：m==matrix.lengthn==matrix[i].length0<=m,n<=100-104<=matrix[i][j],target<=1043.2.2分析既然這是一個(gè)查找元素的問(wèn)題，并且數(shù)組已經(jīng)排好序，我們自然可以想到用二分查找是一個(gè)高效的查找方式。輸入的

mxn

矩陣可以視為長(zhǎng)度為

mxn的有序數(shù)組：行列坐標(biāo)為(row,col)的元素，展開(kāi)之后索引下標(biāo)為idx=row*n+col；反過(guò)來(lái)，對(duì)于一維下標(biāo)為idx的元素，對(duì)應(yīng)二維數(shù)組中的坐標(biāo)就應(yīng)該是：row=idx/n;col=idx%n;3.2.3實(shí)現(xiàn)：二分查找代碼實(shí)現(xiàn)如下：publicclassSearchMatrix{

publicbooleansearchMatrix(int[][]matrix,inttarget){

intm=matrix.length;

if(m==0)returnfalse;

intn=matrix[0].length;

intleft=0;

intright=m*n-1;

//二分查找，定義左右指針

while(left<=right){

intmidIdx=(left+right)/2;

intmidElement=matrix[midIdx/n][midIdx%n];

if(midElement<target)

left=midIdx+1;

elseif(midElement>target)

right=midIdx-1;

else

returntrue;//找到target

}

returnfalse;

}

}復(fù)雜度分析時(shí)間復(fù)雜度:由于是標(biāo)準(zhǔn)的二分查找，時(shí)間復(fù)雜度為O(log(mn))?？臻g復(fù)雜度:

沒(méi)有用到額外的空間，復(fù)雜度為O(1)。3.3尋找重復(fù)數(shù)（#287）3.3.1題目說(shuō)明給定一個(gè)包含

n+1個(gè)整數(shù)的數(shù)組

nums，其數(shù)字都在1到n

之間（包括1和n），可知至少存在一個(gè)重復(fù)的整數(shù)。假設(shè)只有一個(gè)重復(fù)的整數(shù)，找出這個(gè)重復(fù)的數(shù)。示例1:輸入:[1,3,4,2,2]輸出:2示例2:輸入:[3,1,3,4,2]輸出:3說(shuō)明：不能更改原數(shù)組（假設(shè)數(shù)組是只讀的）。只能使用額外的O(1)的空間。時(shí)間復(fù)雜度小于O(n2)。數(shù)組中只有一個(gè)重復(fù)的數(shù)字，但它可能不止重復(fù)出現(xiàn)一次。3.3.2分析怎樣證明nums中存在至少一個(gè)重復(fù)值？其實(shí)很簡(jiǎn)單，這是“抽屜原理”（或者叫“鴿子洞原理”）的簡(jiǎn)單應(yīng)用。這里，nums中的每個(gè)數(shù)字（n+1個(gè)）都是一個(gè)物品，nums中可以出現(xiàn)的每個(gè)不同的數(shù)字（n個(gè)）都是一個(gè)“抽屜”。把n+1個(gè)物品放入n個(gè)抽屜中，必然至少會(huì)有一個(gè)抽屜放了2個(gè)或者2個(gè)以上的物品。所以這意味著nums中至少有一個(gè)數(shù)是重復(fù)的。3.3.3方法一：保存元素法（存入HashMap）首先我們想到，最簡(jiǎn)單的辦法就是，遍歷整個(gè)數(shù)組，挨個(gè)統(tǒng)計(jì)每個(gè)數(shù)字出現(xiàn)的次數(shù)。用一個(gè)HashMap保存每個(gè)數(shù)字對(duì)應(yīng)的count數(shù)量，就可以直觀地判斷出是否重復(fù)了。代碼如下：publicintfindDuplicate1(int[]nums){

Map<Integer,Integer>countMap=newHashMap<>();

for(Integernum:nums){

if(countMap.get(num)==null)

countMap.put(num,1);

else

returnnum;

}

return-1;

}3.3.4方法二：保存元素法改進(jìn)（存入Set）當(dāng)然我們應(yīng)該還能想到，其實(shí)沒(méi)必要用HashMap，直接保存到一個(gè)Set里，就知道這個(gè)元素到底有沒(méi)有了。publicintfindDuplicate2(int[]nums){

Set<Integer>set=newHashSet<>();

for(Integernum:nums){

if(set.contains(num))

returnnum;

else

set.add(num);

}

return-1;

}復(fù)雜度分析時(shí)間復(fù)雜度：O(n)，我們只對(duì)數(shù)組做了一次遍歷，在HashMap和HashSet中查找的復(fù)雜度是O(1)?？臻g復(fù)雜度：O(n)，我們需要一個(gè)HashMap或者HashSet來(lái)做額外存儲(chǔ)，最壞情況下，這需要線性的存儲(chǔ)空間。盡管時(shí)間復(fù)雜度較小，但以上兩種保存元素的方法，都用到了額外的存儲(chǔ)空間，這個(gè)空間復(fù)雜度不能讓我們滿(mǎn)意。3.3.5方法三：二分查找這道題目中數(shù)組其實(shí)是很特殊的，我們可以從原始的[1,N]的自然數(shù)序列開(kāi)始想?，F(xiàn)在增加到了N+1個(gè)數(shù)，根據(jù)抽屜原理，肯定會(huì)有重復(fù)數(shù)。對(duì)于增加重復(fù)數(shù)的方式，整體應(yīng)該有兩種可能：如果重復(fù)數(shù)（比如叫做target）只出現(xiàn)兩次，那么其實(shí)就是1~N所有數(shù)都出現(xiàn)了一次，然后再加一個(gè)target；如果重復(fù)數(shù)target出現(xiàn)多次，那在情況1的基礎(chǔ)上，它每多出現(xiàn)一次，就會(huì)導(dǎo)致1~N中的其它數(shù)少一個(gè)。例如：1~9之間的10個(gè)數(shù)的數(shù)組，重復(fù)數(shù)是6：1，2，5，6，6，6，6，6，7，9本來(lái)最簡(jiǎn)單（重復(fù)數(shù)出現(xiàn)兩次，其它1~9的數(shù)都出現(xiàn)一次）的是1，2，3，4，5，6，6，7，8，9現(xiàn)在沒(méi)有3、4和8，所以6會(huì)多出現(xiàn)3次。我們可以發(fā)現(xiàn)一個(gè)規(guī)律：以target為界，對(duì)于比target小的數(shù)i，數(shù)組中所有小于等于它的數(shù)，最多出現(xiàn)一次（有可能被多出現(xiàn)的target占用了），所以總個(gè)數(shù)不會(huì)超過(guò)i。對(duì)于比target大的數(shù)j，如果每個(gè)元素都只出現(xiàn)一次，那么所有小于等于它的元素是j個(gè)；而現(xiàn)在target會(huì)重復(fù)出現(xiàn)，所以總數(shù)一定會(huì)大于j。用數(shù)學(xué)化的語(yǔ)言描述就是：我們把對(duì)于1~N內(nèi)的某個(gè)數(shù)i，在數(shù)組中小于等于它的所有元素的個(gè)數(shù)，記為count[i]。則：當(dāng)i屬于[1,target-1]范圍內(nèi)，count[i]<=i；當(dāng)i屬于[target,N]范圍內(nèi)，count[i]>i。所以要找target，其實(shí)就是要找1~N中這個(gè)分界的數(shù)。所以我們可以對(duì)1~N的N個(gè)自然數(shù)進(jìn)行二分查找，它們可以看作一個(gè)排好序的數(shù)組，但不占用額外的空間。代碼實(shí)現(xiàn)如下：publicintfindDuplicate3(int[]nums){

intl=1;

intr=nums.length-1;

//二分查找

while(l<=r){

inti=(l+r)/2;

//對(duì)當(dāng)前i計(jì)算count[i]

intcount=0;

for(intj=0;j<nums.length;j++){

if(nums[j]<=i)

count++;

}

//判斷count[i]和i的大小關(guān)系

if(count<=i)

l=i+1;

else

r=i;

//找到target

if(l==r)

returnl;

}

return-1;

}復(fù)雜度分析時(shí)間復(fù)雜度：O(nlogn)，其中n為nums[]數(shù)組的長(zhǎng)度。二分查找最多需要O(logn)次，而每次判斷count的時(shí)候需要O(n)遍歷nums[]數(shù)組求解小于等于i的數(shù)的個(gè)數(shù)，因此總時(shí)間復(fù)雜度為O(nlogn)?？臻g復(fù)雜度：O(1)。我們只需要常數(shù)空間存放若干變量。3.3.6方法四：排序法另一個(gè)想法是，我們可以先在原數(shù)組上排序。排序之后，所有重復(fù)的數(shù)會(huì)排在一起；這樣，只要我們遍歷的時(shí)候發(fā)現(xiàn)連續(xù)兩個(gè)元素相等，就可以輸出結(jié)果了。代碼如下：publicintfindDuplicate3(int[]nums){

Arrays.sort(nums);

for(inti=1;i<nums.length;i++){

if(nums[i]==nums[i-1])

returnnums[i];

}

return-1;

}復(fù)雜度分析時(shí)間復(fù)雜度：O(nlgn)。對(duì)數(shù)組排序，在Java中要花費(fèi)O(nlgn)時(shí)間，后續(xù)是一個(gè)線性?huà)呙?，所以總的時(shí)間復(fù)雜度是O(nlgn)?？臻g復(fù)雜度：O(1)(orO(n))，在這里，我們對(duì)nums進(jìn)行了排序，因此內(nèi)存大小是固定的。當(dāng)然，這里的前提是我們可以用常數(shù)的空間，在原數(shù)組上直接排序。如果我們不能修改輸入數(shù)組，那么我們必須把nums拷貝出來(lái)，并進(jìn)行排序，這需要分配線性的額外空間。3.3.7方法五：快慢指針?lè)ǎㄑh(huán)檢測(cè)）這是一種比較特殊的思路。把nums看成是順序存儲(chǔ)的鏈表，nums中每個(gè)元素的值是下一個(gè)鏈表節(jié)點(diǎn)的地址。那么如果nums有重復(fù)值，說(shuō)明鏈表存在環(huán)，本問(wèn)題就轉(zhuǎn)化為了找鏈表中環(huán)的入口節(jié)點(diǎn)，因此可以用快慢指針解決。比如數(shù)組[3，6，1，4，6，6，2]保存為：整體思路如下：第一階段，尋找環(huán)中的節(jié)點(diǎn)初始時(shí)，都指向鏈表第一個(gè)節(jié)點(diǎn)nums[0]；慢指針每次走一步，快指針走兩步；如果有環(huán)，那么快指針一定會(huì)再次追上慢指針；相遇時(shí)，相遇節(jié)點(diǎn)必在環(huán)中第二階段，尋找環(huán)的入口節(jié)點(diǎn)（重復(fù)的地址值）重新定義兩個(gè)指針，讓before，after分別指向鏈表開(kāi)始節(jié)點(diǎn)，相遇節(jié)點(diǎn)before與after相遇時(shí)，相遇點(diǎn)就是環(huán)的入口節(jié)點(diǎn)第二次相遇時(shí)，應(yīng)該有：慢指針總路程=環(huán)外0到入口+環(huán)內(nèi)入口到相遇點(diǎn)(可能還有+環(huán)內(nèi)m圈)快指針總路程=環(huán)外0到入口+環(huán)內(nèi)入口到相遇點(diǎn)+環(huán)內(nèi)n圈并且，快指針總路程是慢指針的2倍。所以：環(huán)內(nèi)n-m圈=環(huán)外0到入口+環(huán)內(nèi)入口到相遇點(diǎn)。把環(huán)內(nèi)項(xiàng)移到同一邊，就有：環(huán)內(nèi)相遇點(diǎn)到入口+環(huán)內(nèi)n-m-1圈=環(huán)外0到入口這就很清楚了：從環(huán)外0開(kāi)始，和從相遇點(diǎn)開(kāi)始，走同樣多的步數(shù)之后，一定可以在入口處相遇。所以第二階段的相遇點(diǎn)，就是環(huán)的入口，也就是重復(fù)的元素。代碼如下：publicintfindDuplicate(int[]nums){

//定義快慢指針

intfast=0,low=0;

//第一階段：尋找鏈表中的環(huán)

do{

//快指針一次走兩步，慢指針一次走一步

low=nums[low];

fast=nums[nums[fast]];

}while(fast!=low);

//第二階段：尋找環(huán)在鏈上的入口節(jié)點(diǎn)

intptr1=0,ptr2=low;

while(ptr1!=ptr2){

ptr1=nums[ptr1];

ptr2=nums[ptr2];

}

returnptr1;

}復(fù)雜度分析時(shí)間復(fù)雜度：O(n)，不管是尋找環(huán)上的相遇點(diǎn)，還是環(huán)的入口，訪問(wèn)次數(shù)都不會(huì)超過(guò)數(shù)組長(zhǎng)度?？臻g復(fù)雜度：O(1)，我們只需要定義幾個(gè)指針就可以了。通過(guò)快慢指針循環(huán)檢測(cè)這樣的巧妙方法，實(shí)現(xiàn)了在不額外使用內(nèi)存空間的前提下，滿(mǎn)足線性時(shí)間復(fù)雜度O(n)。

第四章字符串問(wèn)題講解字符串（String）是由零個(gè)或多個(gè)字符組成的有限序列，它是編程語(yǔ)言中表示文本的數(shù)據(jù)類(lèi)型。字符串與數(shù)組有很多相似之處，比如可以使用索引（下標(biāo)）來(lái)得到一個(gè)字符。字符串，一般可以認(rèn)為就是一個(gè)字符數(shù)組（chararray）。不過(guò)字符串有其鮮明的特點(diǎn)，它的結(jié)構(gòu)相對(duì)簡(jiǎn)單，但規(guī)?？赡苁欠浅｝嫶蟮?。在編程語(yǔ)言中，字符串往往由特定字符集內(nèi)有限的字符組合而成。在Java中字符串屬于對(duì)象，Java提供了String類(lèi)來(lái)創(chuàng)建和操作字符串。4.1字符串相加（#415）4.1.1題目說(shuō)明給定兩個(gè)字符串形式的非負(fù)整數(shù)

num1和num2

，計(jì)算它們的和。提示：num1和num2

的長(zhǎng)度都小于5100num1和num2都只包含數(shù)字

0-9num1和num2都不包含任何前導(dǎo)零你不能使用任何內(nèi)建BigInteger庫(kù)，

也不能直接將輸入的字符串轉(zhuǎn)換為整數(shù)形式4.1.2分析這里不允許直接將輸入字符串轉(zhuǎn)為整數(shù)，那自然想到應(yīng)該把字符串按每個(gè)字符char一一拆開(kāi)，相當(dāng)于遍歷整數(shù)上的每一個(gè)數(shù)位，然后通過(guò)“乘10疊加”的方式，就可以整合起來(lái)了。這相當(dāng)于算術(shù)中的“豎式加法”。另外題目要求不能使用BigInteger的內(nèi)建庫(kù)，這其實(shí)就是讓我們自己實(shí)現(xiàn)一個(gè)大整數(shù)相加的功能。4.1.3代碼實(shí)現(xiàn)publicclassAddStrings{

publicStringaddStrings(Stringnum1,Stringnum2){

StringBufferresult=newStringBuffer();

inti=num1.length()-1;

intj=num2.length()-1;

intcarry=0;

while(i>=0||j>=0||carry!=0){

intx=i>=0?num1.charAt(i)-'0':0;

inty=j>=0?num2.charAt(j)-'0':0;

intsum=x+y+carry;

result.append(sum%10);

carry=sum/10;

i--;

j--;

}

returnresult.reverse().toString();

}

}4.1.4復(fù)雜度分析時(shí)間復(fù)雜度：O(max(len1,len2))，其中l(wèi)en1=num1.length，len2=num2.length。豎式加法的次數(shù)取決于較大數(shù)的位數(shù)?？臻g復(fù)雜度：O(n)。解法中使用到了StringBuffer，所以空間復(fù)雜度為O(n)。4.2字符串相乘（#43）4.2.1題目說(shuō)明給定兩個(gè)以字符串形式表示的非負(fù)整數(shù)

num1

和

num2，返回

num1

和

num2

的乘積，它們的乘積也表示為字符串形式。示例1:輸入:num1="2",num2="3"輸出:"6"示例

2:輸入:num1="123",num2="456"輸出:"56088"說(shuō)明：num1

和

num2

的長(zhǎng)度小于110。num1和

num2只包含數(shù)字

0-9。num1和

num2

均不以零開(kāi)頭，除非是數(shù)字0本身。不能使用任何標(biāo)準(zhǔn)庫(kù)的大數(shù)類(lèi)型（比如BigInteger）或直接將輸入轉(zhuǎn)換為整數(shù)來(lái)處理。4.2.2分析跟“字符串相加”類(lèi)似，這里我們要處理的，也是大整數(shù)的相乘問(wèn)題。思路也可以非常類(lèi)似：我們借鑒數(shù)學(xué)中“豎式乘法”的規(guī)則，用num1分別去乘num2的每一位數(shù)字，最后再用AddStrings將乘出的結(jié)果全部疊加起來(lái)就可以了。4.2.3具體代碼實(shí)現(xiàn)publicclassMultiplyStrings{

publicStringmultiply(Stringnum1,Stringnum2){

if(num1.equals("0")||num2.equals("0"))return"0";

Stringresult="0";

//遍歷num2的每個(gè)數(shù)位，逐個(gè)與num1相乘

for(inti=num2.length()-1;i>=0;i--){

intcarry=0;

StringBuffercurRes=newStringBuffer();

for(intj=0;j<num2.length()-1-i;j++){

curRes.append("0");

}

inty=num2.charAt(i)-'0';

//遍歷num1的每一位數(shù)，跟y相乘

for(intj=num1.length()-1;j>=0;j--){

intx=num1.charAt(j)-'0';

intproduct=x*y+carry;

curRes.append(product%10);

carry=product/10;

}

if(carry!=0)curRes.append(carry);

AddStringsaddStrs=newAddStrings();

result=addStrs.addStrings(result,curRes.reverse().toString());

}

returnresult;

}

}4.2.4復(fù)雜度分析時(shí)間復(fù)雜度：O(mn+n^2)，其中m和n分別是num1和num2的長(zhǎng)度。做計(jì)算的時(shí)候，外層需要從右往左遍歷num2，而對(duì)于num2的每一位，都需要和num1的每一位計(jì)算乘積，因此計(jì)算乘積的總次數(shù)是mn。字符串相加操作共有n次，每次相加的字符串長(zhǎng)度最長(zhǎng)為m+n，因此字符串相加的時(shí)間復(fù)雜度是O(mn+n^2)?？倳r(shí)間復(fù)雜度是O(mn+n^2)?？臻g復(fù)雜度：O(m+n)?？臻g復(fù)雜度取決于存儲(chǔ)中間狀態(tài)的字符串，由于乘積的最大長(zhǎng)度為m+n，因此存儲(chǔ)中間狀態(tài)的字符串的長(zhǎng)度不會(huì)超過(guò)m+n。4.2.5算法優(yōu)化我們看到計(jì)算過(guò)程中，用到了太多的字符串相加操作，調(diào)用addStrings方法時(shí)又需要遍歷字符串的每一位，這個(gè)過(guò)程顯得有些繁瑣。能不能用其它的方法進(jìn)行簡(jiǎn)化呢？我們發(fā)現(xiàn)，m位數(shù)乘以n位數(shù)，結(jié)果最多就是m+n位；所以我們可以用一個(gè)m+n長(zhǎng)度的數(shù)組來(lái)保存計(jì)算結(jié)果。而且，某兩個(gè)數(shù)位相乘，num1[i]xnum2[j]的結(jié)果(定義為兩位數(shù)，一位數(shù)的話(huà)前面補(bǔ)0)，其第一位位于result[i+j]，第二位位于result[i+j+1]。根據(jù)上面的思路，我們可以遍歷num1和num2中的每一位數(shù)，相乘后疊加到result的對(duì)應(yīng)位上就可以了。代碼實(shí)現(xiàn)如下：publicStringmultiply(Stringnum1,Stringnum2){

if(num1.equals("0")||num2.equals("0"))return"0";

int[]resultArr=newint[num1.length()+num2.length()];

//遍歷num1和num2，逐位計(jì)算乘積，填入結(jié)果數(shù)組中

for(inti=num1.length()-1;i>=0;i--){

intx=num1.charAt(i)-'0';

for(intj=num2.length()-1;j>=0;j--){

inty=num2.charAt(j)-'0';

intproduct=x*y;

inttemp=resultArr[i+j+1]+product;

resultArr[i+j+1]=temp%10;

resultArr[i+j]+=temp/10;

}

}

StringBufferresult=newStringBuffer();

intstart=resultArr[0]==0?1:0;

for(inti=start;i<resultArr.length;i++){

result.append(resultArr[i]);

}

returnresult.toString();

}復(fù)雜度分析時(shí)間復(fù)雜度：O(mn)，其中m和n分別是num1和num2的長(zhǎng)度。需要計(jì)算num1的每一位和num2的每一位的乘積?？臻g復(fù)雜度：O(m+n)，需要?jiǎng)?chuàng)建一個(gè)長(zhǎng)度為m+n的數(shù)組存儲(chǔ)乘積。4.3去除重復(fù)字母（#316）4.3.1題目說(shuō)明給你一個(gè)字符串s，請(qǐng)你去除字符串中重復(fù)的字母，使得每個(gè)字母只出現(xiàn)一次。需保證返回結(jié)果的字典序最小（要求不能打亂其他字符的相對(duì)位置）。示例1：輸入：s="bcabc"輸出："abc"示例2：輸入：s="cbacdcbc"輸出："acdb"提示：1<=s.length<=104s由小寫(xiě)英文字母組成4.3.2分析首先要知道什么叫“字典序”。字符串之間比較跟數(shù)字之間比較是不太一樣的：字符串比較，是從頭往后一個(gè)字符一個(gè)字符比較的，哪個(gè)字符串大取決于兩個(gè)字符串中第一個(gè)對(duì)應(yīng)不相等的字