一、287. 尋找重復(fù)數(shù)

給定一個包含 n + 1 個整數(shù)的數(shù)組 nums，其數(shù)字都在 1 到 n 之間（包括 1 和 n），可知至少存在一個重復(fù)的整數(shù)。假設(shè)只有一個重復(fù)的整數(shù)，找出這個重復(fù)的數(shù)。

1、HashMap

在沒有其它附加條件的情況下，讀者第一時間會想到通過 HashMap 來記錄出現(xiàn)過的數(shù)字，從而找到重復(fù)數(shù)：

上述實(shí)現(xiàn)代碼的時間復(fù)雜度和空間復(fù)雜度都為 O(n)，如果只允許使用 O(1) 的空間復(fù)雜度，該如何解決這道題目呢？

2、Binary Search

這種條件下，最容易想到的就是通過兩重循環(huán)暴力搜索當(dāng)前數(shù)字是否與后面的數(shù)字重復(fù)的方法來解決，但是這種方案的時間復(fù)雜度為 O(n^2)，既然涉及到了搜索，就可以嘗試通過二分搜索算法將時間復(fù)雜度降低到 O(nlogn)。

根據(jù)前面的刷題經(jīng)驗(yàn)，可以很容易地找出有序數(shù)組：1 到 n 的遞增整數(shù)序列。

接下來的難點(diǎn)就是通過重復(fù)數(shù)的特性來確定下一輪搜索區(qū)間是落在左半?yún)^(qū)間還是右半?yún)^(qū)間：

• 首先需要遍歷 nums 數(shù)組，獲取不大于當(dāng)前中間數(shù)的數(shù)字的個數(shù)；

• 如果個數(shù)大于中間數(shù)，那么下一輪搜索區(qū)間落在左半?yún)^(qū)間；

• 如果個數(shù)小于中間數(shù)，那么下一輪搜索區(qū)間落在右半?yún)^(qū)間；

二、209. 長度最小的子數(shù)組

給定一個含有 n 個正整數(shù)的數(shù)組和一個正整數(shù) s ，找出該數(shù)組中滿足其和 ≥ s 的長度最小的連續(xù)子數(shù)組。如果不存在符合條件的連續(xù)子數(shù)組，返回 0。

1、Binary Search

這道題目中的有序數(shù)組不太好找，需要用到一個技巧：構(gòu)造前綴和數(shù)組。

  nums = [2, 3, 1, 2, 4, 3]# 前綴和sums = [0, 2, 5, 6, 8, 12, 15]

從而上述示例中可以發(fā)現(xiàn)前綴和數(shù)組是一個有序數(shù)組，那么對于任意 i 到 j 的連續(xù)子數(shù)組之和，可以通過 sums[j+1] - sums[i] 求出。

并且根據(jù)前綴和的差值與 s 的比較，可以判斷滿足條件的連續(xù)子數(shù)組的終止下標(biāo)落在哪個區(qū)間內(nèi)。

參考視頻：傳送門

通過前綴和對數(shù)組的預(yù)處理以及二分搜索算法，時間復(fù)雜度為 O(nlogn)。

2、Two Points

除了上述二分搜索算法的處理方法之外，可能最簡單暴力的方法就是通過嵌套循環(huán)找出長度最小的連續(xù)子數(shù)組，但是這種方法的時間復(fù)雜度為 O(n^2)，有沒有方法將其降低到 O(n) 的時間復(fù)雜度呢？。

這里就要提及一下滑動窗口算法，它常用于處理連續(xù)子元素問題，將嵌套循環(huán)問題轉(zhuǎn)化為單循環(huán)問題。

在本題中，通過頭指針和尾指針維護(hù)當(dāng)前連續(xù)子數(shù)組的和值窗口：

• 當(dāng)前窗口的和值大于 s ，那么頭指針向后移動一位；

• 當(dāng)前窗口的和值小于 s ，那么尾指針向后移動一位；

三、153. 尋找旋轉(zhuǎn)排序數(shù)組中的最小值

假設(shè)按照升序排序的數(shù)組在預(yù)先未知的某個點(diǎn)上進(jìn)行了旋轉(zhuǎn)。( 例如，數(shù)組 [0,1,2,4,5,6,7] 可能變?yōu)?[4,5,6,7,0,1,2] )。請找出其中最小的元素。你可以假設(shè)數(shù)組中不存在重復(fù)元素。

這一類型的題目在 Easy 中也出現(xiàn)過，如：【852. 山脈數(shù)組的峰頂索引】和【162. 尋找峰值】。

本題中，原本的遞增數(shù)組被轉(zhuǎn)化成包含兩個遞增序列的數(shù)組，并且其中無重復(fù)元素，那么就可以得出：第一個遞增數(shù)組中的任意一個元素都大于第二個遞增數(shù)組中的元素。

有了這一關(guān)鍵信息，對于任一中間數(shù)，都可以將其與當(dāng)前搜索區(qū)間的最后一個元素相比較，從而知道當(dāng)前中間數(shù)在哪一個遞增序列上，而所求的最小值存在于第二個遞增序列的頭部，那么不斷將搜索區(qū)間往這一方向收縮，即可得到最小值：

四、33. 搜索旋轉(zhuǎn)排序數(shù)組

假設(shè)按照升序排序的數(shù)組在預(yù)先未知的某個點(diǎn)上進(jìn)行了旋轉(zhuǎn)。( 例如，數(shù)組 [0,1,2,4,5,6,7] 可能變?yōu)?[4,5,6,7,0,1,2] )。搜索一個給定的目標(biāo)值，如果數(shù)組中存在這個目標(biāo)值，則返回它的索引，否則返回 -1 。你可以假設(shè)數(shù)組中不存在重復(fù)的元素。你的算法時間復(fù)雜度必須是 O(log n) 級別。

這道題是【153. 尋找旋轉(zhuǎn)排序數(shù)組中的最小值】的進(jìn)階題型。

在 153 中，只需要將搜索區(qū)間不斷向第二個遞增區(qū)間收縮，即可得到最小值。而本題中的目標(biāo)值的位置并不確定，所以在每次確定搜索區(qū)間時，需要考慮很多種情況：

• 如果當(dāng)前搜索區(qū)間只落在一個遞增區(qū)間上，那么和一般的處理方法沒什么異樣；

• 如果當(dāng)前搜索區(qū)間橫跨兩個遞增區(qū)間，那么就需要根據(jù)中間數(shù)在第一個遞增區(qū)間還是第二個遞增區(qū)間上分別處理；

具體的條件判斷，請查看下面的代碼實(shí)現(xiàn)：

五、81. 搜索旋轉(zhuǎn)排序數(shù)組 II

假設(shè)按照升序排序的數(shù)組在預(yù)先未知的某個點(diǎn)上進(jìn)行了旋轉(zhuǎn)。( 例如，數(shù)組 [0,0,1,2,2,5,6] 可能變?yōu)?[2,5,6,0,0,1,2] )。編寫一個函數(shù)來判斷給定的目標(biāo)值是否存在于數(shù)組中。若存在返回 true，否則返回 false。

這道題目在【33. 搜索旋轉(zhuǎn)排序數(shù)組】的基礎(chǔ)上去除了”不存在重復(fù)元素“這一條件。

回顧 33 題的解法，在尋找下一個搜索區(qū)間時，通過該搜索區(qū)間的頭部元素和尾部元素的比較得出當(dāng)前搜索區(qū)間是否橫跨兩個遞增序列。一旦沒有無重復(fù)元素這一條件，那么根據(jù)頭尾兩個元素?zé)o法判斷當(dāng)前搜索區(qū)間是否橫跨兩個遞增序列。

本題要求計(jì)算元素的存在性，那么一個元素的重復(fù)元素對其存在性是沒有任何影響的，所以只要在二分搜索的過程中，剔除掉頭尾部的重復(fù)元素即可：

寫在最后

算法作為計(jì)算機(jī)的基礎(chǔ)學(xué)科，用 JavaScript 刷，一點(diǎn)也不丟人ε=ε=ε=┏(゜ロ゜;)┛。

本系列文章會分別給出一種算法的3種難度的總結(jié)篇（簡單難度，中等難度以及困難難度）。在簡單難度中，會介紹該算法的基本知識與實(shí)現(xiàn)，另外兩個難度，著重講解解題的思路。

如果本文對您有所幫助，可以點(diǎn)贊或者關(guān)注來鼓勵博主。