1.雙指針

總結：

1.復寫0這道題，告訴我們要正難其反，我們從后向前進行重寫，刪除某些數字的時候，我們可以從前向后遍歷，但是增加一些數字的時候會對后面的數據進行覆蓋，所以要從后向前進行

2.快樂數涉及到環的題目第一就要想到快慢雙指針

3.? 1.3到1.7這幾道題其實都是利用了單調性的性質，在暴力枚舉的基礎上，節省了時間復雜度

1.1.復寫0

解題思路：

1.這道題遇到0就會向后進行覆寫操作，所以我們按照正常的思路從前向后便利的時候，

遇到0，進行覆寫，就會將0后面的數字進行覆蓋，造成數據的丟失

所以我們要正難其反，我們從后向前進行重寫，

所以我們就引出了第二個問題，如何在數組中找到變型后的最后一位數字

2.如何在數組中找到變型后的最后一位數字，定義兩個指針，cur和ret，ret起始為-1，cur為0，cur從前向后進行遍歷，arr【cur】==0，ret+=2；反之 ret+=1；

代碼實現：

注意點：

1.ret判斷的結束條件一定在cur++的前面

2.邊界情況

當我cur指向的最后一個數字是0的時候，ret是連休跳兩格，所以要處理邊界情況

1.2.快樂數

解題思路：

1.我們都會發現，給定的數都會最后進入一個循環當中，要么是一個不包括數字1的循環，要么是一個只包括數字1的循環

2.涉及到環的題目第一就要想到快慢雙指針，fast和last fast一次走兩步，last一次走一次，最后一定會相遇，此時相遇以后跳出循環，判斷2遇到的值是否是1即可

代碼實現：

1.3.盛最多水的容器

解題思路：

1其實這道題要要使用單調性來做，定義兩個指針，一個是left左區間，right右區間

假設此時left在0下標，right在n-1下標，

那么此時的? V=L*H

此時我的L是最大的，但是我的高度是以較小值為基準，

若此時? 以最小值的高度和其他下標進行匹配，只會出現以下兩種情況

V=L（減小）* H（不變）；

V=L（減小） *H（減小）；

所以我們此時如果還用較小的高度和其他下標進行匹配，結果一定是變小的，

所以此時我們可以直接跳過跳過較小的一方，

這樣循環，直到left==right結束

代碼實現：

1.4.有效三角形的個數

解題思路：

判斷三條邊是否能構成三角形，只需判斷 A+B>C(最大的邊)

所以就轉換成在一個數組中固定一個最大的數，再找其他兩條邊的問題

所以此時我們就要想到使用單調性的性質，

假設此時是一個有序的數組，

我們從后向前依次固定最大數然后在最大值的左區間找匹配的另外兩條邊即可

此時有兩種情況：

情況一：A+B>C：因為數組是有序的，所以A下標到B下邊-1的區間的數據都是符合條件的，

算出區間的大小進行累加，再將第二大的邊進行--；即可

情況二：A+B<C：A向前走一步即可

代碼實現：

1.5.和為 s 的兩個數字

代碼實現：

1.6.三數之和

解題思路：

其實思路和之前的求有效個數的三角形是一樣的，從后往前依次固定一個數，再在其左區間找到符合條件的另外兩個數，也是也運用了單調性的性質

代碼實現：

注意點：

?此時的要求是不能有重復的數據組

1.當遇到符合條件的數據組的時候，此時的left要向前尋找一個新的值，right要向后尋找一個新的值

此時還要主意一點就是注意數組越界的問題

2.當一個固定的值結束以后，固定值也是要跳過相同的值，尋找新的值

此時就不可以兩邊都對i進行移動，防止錯過合適的數據組

1.7.四數之和

解題思路：

代碼的思路其實就是在三數之和的基礎上多套一層，多了一個固定的數而已

代碼實現：

注意點：

注意點1：依舊是 去重+防止越界

注意點二：數據太大，改成long long類型

2.滑動窗口

總結：

使用場景：

當題目給定一個數組，讓你在數組中尋找的符合條件的子區間，此時我們就可以使用滑動窗口來解決這道問題。

滑動窗口的行為：定義兩個指針left和right，分別表示子區間的區間和右區間，兩個指針都是從前向后進行移動，直到右區間超出了數組的范圍才結束

所以可以到得出一個結論，這個數組一定是單調的（這里的單調并不是升序，降序的表面含義）當right向右走（范圍擴大）離我們要符合的目標值就更進一步，當left向右走（范圍變小）離我們要符合的目標值就更遠一步，

分類：

滑動窗口分成動態的滑動窗口（大小可變）和動態的滑動窗口（大小不變）

2.6是靜態的，其余都是動態的

2.1.長度最小的子區間

解題思路：

1.其實我們一開始想到的思路就是，我定義兩個指針 left 和right 將數組中所有的子數組都列舉出來，就可以找到最小的長度，但是一定會超出時間限制

2.此時我們就想想，在哪里可以做出一些優化，

ret:長度

sum：記錄區間的值

left：左區間

right:右區間

第一點：數組都是正數，只要區間變大（right向右移動），sum和就一定會變大，反之（left向右移動）變小，

所以我們會遇到兩種情況，

sum<target:right向右移動，時sum變大

sum>=target:left位置給去除，left++，此時right從left從新開始記錄

注意：此時要優化的點就是right不需要再次重新從left位置進行記錄，

right再次重新從left位置向前走，無非時再次記錄重復的區間

所以

當left位置給去除，left++，

又會出現兩種情況

sum>=target：再次進行更新即可

sum<target:繼續尋找符合要去的區間，right向右移動

代碼實現：

細節注意：

1.求最小值，一開始就定義最大值，返回階段要對結果進行判斷

2.縮小左區間的時候，要一直縮小到sum重新小于目標值為止，記得更新右區間

2.2.無重復字符的最長字串

解題思路：

這道題和上道題很相似，統計子串的最長的長度，所以同向的雙指針可以解決這道問題

代碼實現：

細節注意：

1.數組模擬hash表

2.代碼的執行順序

1.先更新右窗口

2.判斷是否符合條件

3.更新長度

原因：在不斷更新右區間的過程，有兩種情況

1.加入后依舊不重復，不用更新left，直接更新結果

2.加入后重復，更新left，更新結果也沒事，此時找的時最大的區間，left向右移動，一定是減小長度，len不會被影響

3.如果不符合條件的話，下一次left的起始位置時重復的下一個字符

4.判斷是否符合條件時，判斷新加入的字符映射的hash表的個數是否已經大于1

2.3.最大連續1的個數

解題思路：

此時我們要將此題目進行轉變成

在數組中找到一個最大的子區間，其中子區間的中0的個數不能超過k

此時就是我們熟悉的找到一個最長的連續子區間，利用單調性，使用滑動窗口來解決此題目·

代碼實現：

2.4.將減到0的最小操作數

解題思路：

正難則反：題目要我們在最左邊和最右邊找到兩個區間，這倆區間的值加起來等于目標值，

我們就可以轉換成，在數組中找到一個子區間，這個區間的值等于count-x,但是要這個區間的長度最長的問題

代碼實現：

細節注意：

1.邊界問題：

count-x=負數：不存在，直接返回-1

count-x==0：直接返回數組的大小即可

2.湊不出的情況：

2.5.水果成藍

解題思路：

其實這道題的意思就是找到一個最長的子區間，其中的種類不能超過兩種，

同向雙指針，滑動窗口

代碼實現：

細節：

容器的使用:

1.種類是否超出限制 使用size（）

2.刪除種類，使用 erase

2.6.找到字符串中所有字母異位詞

解題思路：

這個滑動窗口的思路比之前的更加的明顯，因為此時窗口的大小是不變的，一直以p，size（）的大小一直向后進行移動

代碼實現：

細節：

1.中間有個步驟比較兩個hash1和hash2是否相同，相同的話就是符合條件反之不符合

但是如果我們是對兩個hash表進行遍歷，來進行比較，效率太低了

此時我們定義一個count值，count出現的地方右三處，用于記錄有效字符的個數

1.在進窗口的時候

hash2【字符】小于hash【字符】的個數的話，count就++

2.在出窗口的時候

hash2【字符】小于等于hash【字符】的個數的話，count就--

3.判斷區間是否是合法區間

count==給定字符串的個數，那么此時就是合法區間

2.7.串聯所有單詞的子串

解題思路：

這道題其實是可以轉換成找到字符串中所有字母異位詞

我們只需要將將words[i].length 個字符看作成一個整體

代碼實現：

細節處理：

1.根據words?中所有字符串?長度相同，而且字符串?s是由words?中的單詞所組成，所以我們就可以這道題轉化成找到字符串中所有字母異位詞來做，

大體的的要循環words字符串?長度，

2.left和right下標的移動也是以一個len為一個單位進行移動

3.使用字符串容器接口，取指定位置的子字符串

2.8.最小的覆蓋子串

解題思路：

和之間一樣定義兩個雙指針，從左往右進行遍歷，，不斷的更新最小的區間

代碼實現：

細節處理：

1.此時的count不是和之前記錄有效字符的個數，而是記錄有效字符的種類

因為之前題目的子區間中的字符個數個數是一 一對應的，但是此時假設我原數組中只有一個A，

但是我子區間有兩個A，這樣的子區間也是符合條件的

3.二分查找

總結：

是否能夠使用二分查找，看看數組是否具有二段性，再進行判斷是是使用哪個二分模版

使用情景：

當數據具有二段性的時候我們就可以使用二分查找的算法，此時的二段性并不是代表數組有序的意思。

在3.1~3.4中，數組是有序是，所以此時他們的二段性是：小于更新左區間，大于更新右區間

3.5和3.6，數組并不有序，但是它的二段性是：前一個小于后一個更新左區間，前一個大于后一個更新右區間

3.7中，也是無序的，但是二段性是找出一個基準值：大于基準值更新左區間，小于基準值更新右區間

3.8中，的二段性是根據index和arr【index】是否相等來確定

模版分類：

樸素二分：

樸素二分，就是將具有二段性的數組三部分：小于target， 等于taeget ，大于target

注意點：循環結束條件：left<right, 每次的移動：left=mid+1；? 和? right=mid-1；

查找區間左端點模版：

找到符合條件的最左邊的位置

此時就是將數組分成 小于target 和 大于等于target 兩部分，

mid落在 小于target的時候，left=mid+1；left是一直在試圖跳出不符合這個target的區間，

mid落在 大于等于target的時候，right=mid；right只能不斷的靠近左區間，并不會跳出這個區間

注意：

1.循環的結束條件：left<right;當left==right的時候就是最后的結果

2.mid=left+（right-left）/ 2;個數是偶數的時候，mid位置靠左，防止死循環

查找區間右端點模版：

找到符合條件的最右邊的位置

此時就是將數組分成 小于等于target 和 大于target 兩部分，

mid落在 大于target的時候，right=mid+1；right是一直在試圖跳出不符合這個target的區間，

mid落在 小于等于target的時候，right=mid；right只能不斷的靠近右區間，并不會跳出這個區間

注意：

1.循環的結束條件：left<right;當left==right的時候就是最后的結果

2.mid=left+（right-left+1）/ 2;個數是偶數的時候，mid位置靠右，防止死循環

3.1.二分查找

解題思路：

這道題就是經典的樸素的二分算法

代碼實現：

細節分析：

3.2.在排序數組中查找元素的第一個和最后一個位置

解題思路：

先將數組分成?小于target 和 大于等于target 兩部分，找到最左邊的值，

再將數組分成 大于target 和 小于等于target 兩部分，找到最右邊的值

代碼實現：

細節分析：

1.處理邊界情況：

2.不存在的情況，要對下標進行驗證

3.3.搜索插入的位置

解題思路：

如果目標值都存在的話就是，就使用樸素的二分算法，

但是此時有可能target這個值不存在就需要返回,如果存在本該插入的位置，也就是大于target最近的位置，

所以此時我們就可以將數組分成?小于target 和 大于等于target 兩部分，找到最左邊的值，

代碼實現：

細節：

當目標值不存在，并且比所有的值都要小的時候，left和right會停在起始位置，是我們最終的結果，不需要特殊處理，但是如果此時目標值比所有的值都要大，left和right停在n-1的位置，但是插入的位置是n，所以對這需要特殊處理一下

3.4.x的算術平方根

解題思路：

要求x的算術平方根，暴力的解決方法就是，從0向后一直進行遍歷，直到一個數的平方，大于x，

所以我們就可以找到一個區間，1~x，這個區間，將這個區間分成，小于等于target 和 大于target 兩部分，進行二分查找

代碼實現：

細節處理：

1.處理0

2.換成 long long 擴大范圍

3.5.山脈數組的峰頂索引

解題思路：

并不是說數組有序才能使用二分查找算法，只要數組具有二段性，我們就可以使用二分查找算法，

下面這個數組就是天然的二段性，前面的 arr[i]>arr[i-1]? ,后面的? arr[i]<arr[i-1]

所以

就將數組分成arr[i]>arr[i-1]? ,?arr[i]<arr[i-1] 兩部分，并尋找arr[i]>arr[i-1]?的最右區間

代碼實現：

3.6.尋找峰值

解題思路：

這道題和上道題的唯一的一個差異就是，上道題只有一個峰值，這道題有多個峰值

其實都一樣，找出其中的二段性，選擇 mid 和mid-1的位置

1.當 nums[mid-1]<nums[mid]:右邊的區間一定有峰值，left=mid;

2.當 nums[mid-1]>nums[mid]:左邊的區間一定有峰值，right=mid-1；

代碼實現：

代碼的實現其實和上道題一模一樣

3.7.尋找旋轉排序數組中的最小值

解題思路：

c是我們要找的值，

此時我們以D位置的值為基準點，A~B區間的值都比D要大，C~D都是小于等于D，

所以此時這就是是我們要尋找的二段性，

1.mid落在A~B區間 ，left=mid+1；

2.mid落在C~D區間 ，right=mid；

代碼實現：

3.8.點名

解題思路：

可以發現此時的二段性是與數組的下標是有關系的，

在沒有缺失數字之前，index==arr[index]，是相同的，反之后面便不是對應的

根據此時的二段性，

1.mid落在對應的區間，left=mid+1；

2..mid落在不對應的區間，right=mid；,因為此時要尋找不對應的右區間

代碼實現：

細節處理：

有可能·缺失的是最后一個數，此時的邊界情況需要處理

4.前綴和

總結：

前綴和：就是為了快速的求出一段連續的區間的和

4.1.一維數組前綴和模板

解題思路：

第一步：預處理一個前綴和數組

dp[ i ] 表示：表示 [1,i ]區間的所有元素和;

dp[ i ]=dp[ i-1 ]+arr[ i ];

第二步：前綴和數組使用

[ L, R ] ---->dp[R]-dp[L-1]?;

代碼實現：

細節處理：

為什么要對dp數組和arr數組初始化一個虛擬的節點？

為了處理邊界情況：當我們默認arr【0】=0和dp【0】=0，arr數組和dp數組都是從下標為 1開始初始化，就不會出現 dp【-1】和arr【-1】的情況。

4.2.二維數組前綴和模板

解題思路：

1.預處理一個前綴和矩陣

dp[i]j] 表示:從[1,1]位置到 [i,j] 位置，這段區間里面所有元素的和

初始化方程：dp[i]j] =dp[i-1]j]+dp[i]j-1] +arr[i]j] -dp[i-1]j-1]

2.使用前綴和矩陣

給出了 兩個坐標

結果：dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1]

代碼實現：

細節處理：

依舊是多開辟出，最上層的一行和最左邊的一列

4.3.尋找數組的中心下標

解題思路：

根據題意可知，

假設我們此時的下邊為3

左側數之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，
右側數之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，

兩者都沒有加上下標為3的數組位置，

所以我們可以定義兩個dp數組

一個是前綴和數組，一個是后綴和數組

前綴和狀態轉移方程：dp1[i]=dp[i-1]+arr[i];

后綴和狀態轉移方程：dp2[i]=dp2[i+1]+arr[i];

代碼實現：

代碼實現：

在前綴和中dp1[0]和dp2[n-1]默認為0，不進入循環

4.4.除自身以外數組的乘積

解題思路：

其實這道題的思路和上道題一摸一樣

所以我們可以定義兩個dp數組

一個是前綴積數組，一個是后綴積數組

前綴積狀態轉移方程：dp1[i]=dp[i-1]*arr[i];

后綴積狀態轉移方程：dp2[i]=dp2[i+1]*arr[i];

代碼實現：

細節處理：

此時dp1[0]和dp2[0]都要初始化為1

4.5.和為K的子數組

解題思路：

這道題，可能大家都和我一樣，首先想到的解法是滑動窗口，雙指針的思想，但是這道題并不可以使用雙指針，

注意：雙指針的特性：left和right都是向前進行移動，進窗口就表示增加，出窗口就表示減少，但是這道題的范圍是有0和負數的

這道題還是使用前綴和的思想，

第一步：定義一個指針i，使指針從前向后，進行遍歷，找到一個位置，就計算他的前綴和，

sum:代表i位置的前綴和，

第二步：在i位置之前找到sum-i的前綴和，但是如果硬找的話，時間復雜的還是n的平方，

所以要借助一個hash表，來存儲，前綴和和它對應的個數，

代碼實現：

魔鬼細節處理：

1.前綴和加入哈希表的時機?
在計算i位置之前，哈希表里面只保存[0,i-1]位置的前綴和

2.不用真的創建一個前綴和數組
用一個變量 sum 來標記前一個位置的前綴和即可

3.如果整個前綴和等于k 呢?

提前在hash表中的 hash[ 0 ]=1;

4.6.和可被 K 整除的子數組

解題思路：

補充兩個知識點：

1.同余定理：

a%p和b%p的余數是一樣的

2.負數的修正

a%b：a如果是一個復數的話，結果是一個負數，

所以-->a%b+b：但是此時a如果是一個正數的話就不行

所以：（a%b+b）%b；

有了這里兩個知識點以后，這道題的解題的思路就是上道題是一樣的

代碼實現：

細節處理：

3.如果整個前綴和等于k 的倍數呢?

提前在hash表中的 hash[ 0 ]=1;

4.7.連續的數組

解題思路：

依舊是因為此時的數組中有0的存在，所以不能使用滑動窗口的思想來做

根據題目的意思：數組中不是1就是0

我們此時可以將所有的0給的換成-1，

此時題目就轉換成了：找出數組中最長的字串，此字串的和為0，就是 4.5了

代碼實現：

細節處理：

此時需要的最后結果是長度

1.此時的hash表中，第一個存入的是前綴和，第二個存入的是前綴和的下標

2.如果整個前綴和等于k 呢?

提前在hash表中的 hash[ 0 ]=-1;

3.如果遇見的相同的前綴和要更新前綴和嗎？

只更新結果，不加入到hash表中，因為越前的長度，一定比越后面的長度要長

4.8.矩陣區域和

解題思路：

給定一個范圍，讓我們求解這個矩形范圍的數據和，第一時間想的的解法就是使用前綴和，但是這道題是二維前綴和

代碼實現：

細節處理：

注意下標的映射關系，在原數組中和要提交的數組中，數據都是滿的，但是dp數組中最上的和最左邊的數據都是空的