目錄

1. 長度最小的字數組

題解

代碼

?2.無重復字符的最長子串

題解

代碼

3.最大連續1的個數 III

題解

代碼

4.將 x 減到 0 的最小操作數

題解

代碼

---

1. 長度最小的字數組

題目鏈接：209.長度最小的字數組

題目分析:

給定一個含有 n 個 正整數 的數組和一個正整數 target 。

找出該數組中滿足其總和大于等于 target 的長度最小的 子數組 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其長度。如果不存在符合條件的子數組，返回 0 。

（子數組：是連續的！！！）

示例 1：

輸入：target = 7, nums = [2,3,1,2,4,3]
輸出：2
解釋：子數組 [4,3] 是該條件下的長度最小的子數組。

示例 2：

輸入：target = 4, nums = [1,4,4]
輸出：1

---

題解

• 注意題目說的是 正整數 數組，說明數組里面的數是大于等于0的數。

• 因此這道題我們有一種優化的方法。
• 題目讓找連續的子數組和>=target，并且長度最小。有很多種情況，但是我們選擇的是 最小長度。

算法原理：

不管什么題，首先我們一定會先想到的是 暴力求解，因為只有暴力求解出來了，我們就可以在暴力求解的基礎上進行優化~

解法一：暴力枚舉出所有的子數組的和

兩層for循環，O(N^2)

for(int i=0;i<n;i++)for(int j=i;j<n;j++)sum+=num[j];
//固定一個數，挨個往后加if(sum>=target)min(len,j-i+1)

注意到此時暴力枚舉是有優化的。

題目說的是一個 正整數數組，都是大于等于0的數，這個 sum是呈現出遞增的狀態的，單調遞增!

在暴力求解中，此時right還要++，但是注意題目本來要求的就是 最小長度

此時sum在加上往上走了一步的right的num[right]，一定是滿足sum>=target，但是len變成5了，一定不會是最終結果

因此當條件已經滿足sum>=target ，right就不用動了。right后面也就不用再枚舉了。

那現在讓 left+1，right和left指向同一下標，然后再重復上面過程，那有個問題，這段區間的和能不能直接算出來？

• 當然可以。
• 現在sum=8，我只需要把讓sum減去num[left]，不就是現在left和right所在的區間和算出來嗎。
• 沒有必要讓right傻傻的回退然后重新加。因此right不動，更新sum=6.

因此我們從暴力枚舉中發現兩個優化：

• 一個是right 滿足后，后面不用枚舉
• 一個left++，right不用回退，

所以我們可以利用單調性，使用雙指針優化。

---

解法二：利用單調性，使用 “同向雙指針” 來優化

當我們在暴力枚舉的策略中發現left和right都是從左向右一個方向移動，我們就稱為這兩個指針叫做同向指針。同向雙指針又稱為滑動窗口。

什么是滑動窗口？

本質上是 “同向雙指針”，left從左到右移動，right不回退，從左到右移動，用left和right一直 維護這個區間的和，然后這兩個指針從左向右移動的過程非常像一個窗口在這個數組里滑來滑去。

什么時候用滑動窗口？

利用單調性，用滑動窗口解決問題。

當我們發現在暴力求解時，兩個指針都可以做到 不回退，都是向同一個方向移動的時候，此時就可以用滑動窗口。

滑動窗口怎么用？

1. 初始left=0，right=0，充當窗口左端點，右端點。用left，right標記窗口左區間，右區間。
2. 右窗口（++right）（右值進窗口）
3. 判斷

• • 根據判斷決定是否 左窗口(++left)（左值出窗口）

1. 更新結果

• • 2，3都有可能會更新結果，看題目要求

左窗口，判斷，右窗口一直循環，直到right 超過區間長度結束，更新結果看題目要求(右窗口，左窗口都有可能)，。

滑動窗口正確性

• 暴力枚舉肯定對的，因為已經把所有子數組的情況都找出來了。
• 雖然滑動窗口并沒有把沒有把所有情況都枚舉出來，但是這里利用單調性，規避了沒有必要的枚舉
• 雖然沒有把所有情況真正枚舉出來，但是已經判斷出有些子數組不是最終結果，已經把所有結果都考慮進來了，所以這種策略是跟暴力枚舉是一樣正確的。

滑動窗口時間復雜度

進窗口是一個循環，判斷也是一個循環。

兩層循環套在一起。可能會覺得時間復雜度O(N^2)，但是不能看代碼算時間復雜度，要看實際情況分析實際復雜度。

實際我們只會讓right向前移動，left也向前移動，即使時最壞情況，right移動到最后一個元素，left 也移動到最后一個元素，因為單調性，總共也就操作了 n+n=2n 次 整體時間復雜度O(N)。

---

代碼

要考慮到，棧溢出（heap-buffer-overflow） 的邊界情況

可詳見前文

在Leetcode中，無窮大和無窮小分別怎么表示

C/C++中可以使用INT_MAX和INT_MIN

---

?2.無重復字符的最長子串

題目鏈接：3. 無重復字符的最長子串

題目分析:

給定一個字符串 s ，請你找出其中不含有重復字符的 最長 子串 的長度。

示例 1:

輸入: s = "abcabcbb"
輸出: 3 
解釋: 因為無重復字符的最長子串是 "abc"，所以其長度為 3。

示例 2:

輸入: s = "bbbbb"
輸出: 1
解釋: 因為無重復字符的最長子串是 "b"，所以其長度為 1。

示例 3:

輸入: s = "pwwkew"
輸出: 3
解釋: 因為無重復字符的最長子串是 "wke"，所以其長度為 3。請注意，你的答案必須是 子串 的長度，"pwke" 是一個子序列，不是子串。

---

子串和子數組都是連續的

??? 模擬分析示例：

題解

算法原理：

首先還是暴力枚舉，然后根據暴力枚舉進行優化。

• 以下面為例，兩層for循環，但是下面找到的結果都是我們站在上帝角度，編譯器并不知到什么時候結束。
• 一般對應判斷是否有重復元素，我們都可以用哈希表來解決問題。
• 使用哈希表，判斷是否有重復元素，比如讓你判斷一個數組是否有重復，或者兩個數組是否有重復都可以用哈希映射！

解法一：暴力枚舉+哈希表(判斷字符是否重復出現)

O(N^2)

根據解法一做優化，定義一個left，right指針。當right走到有重復的元素后，已經找到一個字串，其中left到right區間每個元素都已經進入hash表。

此時left向前走一步，但是這個區間還是有重復元素，因此left要走到沒有重復的區間才行，

然后這個時候以前做法是right回退然后重新往下走，但是這里left到right區間元素本來就在hash表里

因此就不需要right回退了，而是向right繼續向前走。然后重復上面過程，直到right走到結尾。結束~

這不就是滑動窗口的思想嗎。雙向指針，left往前走，right不回退一直往前走

解法二：利用規律，使用 “滑動窗口” 解決問題

1. left=0，right=0
2. 進窗口
3. 判斷

• • 出窗口

1. 更新結果

進窗口、判斷、出窗口，更新結果是一個大循環過程。直到right到結尾循環結束。

其中判斷、出窗口是一個小循環（直到跳出重復字符）。不過時間復雜度還是O(N).

注意：

• 更新結果可能在? 進窗口后，判斷后，出窗口后，判斷后任意一個地方，看題目要求

本題：

• 進窗口 ->-> 讓字符進入哈希表
• 判斷-> 窗口內出現重復元素
• 出窗口-> 從哈希表中刪除該字符

---

代碼

class Solution {
public:int lengthOfLongestSubstring(string s) {//！！if(s.empty()) return 0; // 處理空輸入vector<char> str;for(char c:s) str.push_back(c);int left=0,right=0,n=str.size(),len=0;//unordered_set ret;unordered_set<char> ret;while(right<n){
//先檢查while(ret.count(str[right])){ret.erase(str[left]);left++;//利用了連續性//表中 發現了右元素已存在//要在左邊 進行跳過}
//不存在 就插入ret.insert(str[right]);len=max(len,right-left+1);right++;}return len;}
};

總結一下：

利用單調性，使用 雙指針 解決問題。

• 一般left和right，一個指向數組最左邊，一個指向數組最右邊，然后一次可以排除一批，再然后left++，–right，兩個指針是對撞的。

這里利用單調性或者利用規律，使用 滑動窗口 解決問題

• 滑動窗口也使用雙指針解決問題，不過left一直從前往后走，right不回退從前往后走，兩個指針是同向的。因此滑動窗口本質其實是 同向雙指針。

---

3.最大連續1的個數 III

題目鏈接：1004. 最大連續1的個數 III

題目分析:

給定一個二進制數組 nums 和一個整數 k，假設最多可以翻轉 k 個 0 ，則返回執行操作后 數組中連續 1 的最大個數 。

示例 1：

輸入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
輸出：6
解釋：[1,1,1,0,0,1,1,1,1,1,1]
粗體數字從 0 翻轉到 1，最長的子數組長度為 6。

示例 2：

輸入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
輸出：10
解釋：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗體數字從 0 翻轉到 1，最長的子數組長度為 10。

---

題解

題目說的翻轉實際上是把0變成1的意思，最多翻轉K次，說明小于等于K都是可以的。

拿到題我們開始肯定想的是暴力求解。

如果直接暴力求解，遇到0->1了，那下一次在遍歷就有問題了。

因此我們換一個思路。這道題不是讓轉化后最大連續1的個數嗎。

我們轉化為：找出最長的子數組，數組里0的個數不超過K個，這個數組里面0一定能夠轉化成1。

算法原理：

解法一：暴力枚舉+zero計數器

偽代碼，兩層for循環，統計zero的個數，滿足zero>k，統計此時數組長度，然后重新進入循環，注意每次zero都清0

for(int i=0;i<n;++i)for(int j=i;j<n;++j)//雙指針 查找出一段區間if(nums[j]==0)++zero;if(zero>k)ret=max(ret,right-left+1)

然后我們根據暴力枚舉，看看有沒有優化的可能。

定義兩個指針left，right，right走到zero>k的位置，zero=3，大于k。

按照暴力求解left++，然后right回溯然后重新往后走。但是我們發現沒有必要，現在left往前走一步，你會發現，right還是停留在老位置，這個區間不用在管的，直接丟棄。

因此，讓left一直走到zero<=k的位置。然后 right也根本不用回溯 然后在重新走，而是直接往后走就行了。

根據上面的發現，當在暴力枚舉中，發現left，right是同向移動的，利用這個規律，使用滑動窗口解決問題

解法二：利用規律，使用滑動窗口

1. left=0，right=0
2. 進窗口
3. 判斷

• • 出窗口

1. 更新結果

進窗口 -> 如果是1，不理會。如果是0，計數器+1

判斷 -> zero>k

出窗口 -> 如果是1，不理會。如果是0，計數器-1

更新結果：在判斷之后在更新

代碼

class Solution {
public:int longestOnes(vector<int>& nums, int k) {int left = 0, right = 0, zero = 0;int n = nums.size(), len = 0;while (right < n) {//進 窗口if (nums[right] == 0)zero++;while (zero > k) {//循環判斷if (nums[left] == 0)zero--;left++;}len = max(len, right - left + 1);right++;}return len;}
};

---

4.將 x 減到 0 的最小操作數

題目鏈接：1658. 將 x 減到 0 的最小操作數

題目分析:

給你一個整數數組 nums 和一個整數 x 。每一次操作時，你應當移除數組 nums 最左邊或最右邊的元素，然后從 x 中減去該元素的值。請注意，需要 修改 數組以供接下來的操作使用。

如果可以將 x 恰好 減到 0 ，返回 最小操作數 ；否則，返回 -1 。

示例 1：

輸入：nums = [1,1,4,2,3], x = 5
輸出：2
解釋：最佳解決方案是移除后兩個元素，將 x 減到 0 。

示例 2：

輸入：nums = [5,6,7,8,9], x = 4
輸出：-1

示例 3：

輸入：nums = [3,2,20,1,1,3], x = 10
輸出：5
解釋：最佳解決方案是移除后三個元素和前兩個元素（總共 5 次操作），將 x 減到 0 。

---

題解

這道題讓每次從數組左右兩邊移除一個數，然后就是一個新的數組，然后再從新的數組再從左右兩邊移除一個數。

• 但是如果真的硬著頭皮開始做，其實是很困難的。
• 并不知道每次是從最左邊走還是最右邊找。有可能這次左邊下次右邊或者還是左邊，情況太復雜了。

因此我們可以利用 正難則反 的思想

• 正對面解題太難，那就想對立面，換個思路。
• 不是每次從左右兩端找一個數嗎，那可能找到情況就是a+b=x，a、b什么情況都要，但是中間這個連續區間的和不也是確定的嗎sum-x
• 也就是這道題我們轉換成，找出最長的子數組長度，所有元素的和正好等于sum-x，然后數組總長減去這段子區間長度不就是問題答案嗎
• 如果沒找到說明這個數組不存在將x減到0的數，直接返回-1

解法一：暴力求解

初始left，right指向同一下標，當right走到和大于target的時候，left往前走

按照暴力求解，right要回到和left相同下標，然后right在重新往前走，直到再次走到和大于target的地方停下來，然后重復上面過程。

• 但是今天這里不需要right回溯，因為right回溯后重新走到下面的位置，因為left已經往前走了，這段區間的和肯定是更小了
• 因此就不需要right回溯了。要么right不動，要么right往后走。
• 同向雙指針 ----> 本質就是滑動窗口

解法二：使用滑動窗口

代碼

class Solution {
public:
int minOperations(vector<int>& nums, int x)
{if(nums.empty()) return -1;int sum=0;for(auto c:nums)sum+=c;// 新增邊界條件處理if (sum == x) return nums.size();  // 整個數組和正好等于xif (sum < x) return -1;            // 總和不足，無法達成目標int target=sum-x,len=0;int left=0,right=0,n=nums.size(),add=0;while(right<n){add+=nums[right];while(add>target){add-=nums[left];left++;}if(add==target)len=max(len,right-left+1);right++;}//！！！len>0      return (len > 0) ? (nums.size() - len) : -1;
}
};

測試樣例跑不全時，要注意對 邊界情況 的處理

• 若不存在這樣的子數組（len = 0）