LeetCode 1004題 “最大連續1的個數 III” 是一道關于數組和滑動窗口的問題。題目描述如下：

題目描述

給定一個由若干 0 和 1 組成的數組 nums，以及一個整數 k。你可以將最多 k 個 0 翻轉為 1。返回經過翻轉操作后，數組中連續 1 的最大個數。

示例：

• 輸入：nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
• 輸出：6
• 解釋：將中間的兩個 0 翻轉為 1，得到最長連續 1 的子數組 [1,1,1,0,0,1,1,1,1,1,1]，長度為 6。

解題思路：滑動窗口

這道題可以通過滑動窗口算法高效解決。核心思路是：找到一個最長的子數組，其中最多包含 k 個 0。如果窗口內的 0 數量超過 k，則需要收縮窗口左側。

具體步驟如下：

1. 擴展窗口：不斷向右移動右指針 right，并統計窗口內 0 的數量。
2. 收縮窗口：如果窗口內 0 的數量超過 k，則向右移動左指針 left，并減少窗口內 0 的數量，直到窗口內 0 的數量不超過 k。
3. 記錄最大長度：在每次窗口合法（0 的數量 ≤ k）時，更新最大長度。

代碼實現

以下是使用滑動窗口解決該問題的代碼：

class Solution {
public:int longestOnes(vector<int>& nums, int k) {int n = nums.size();int left = 0, right = 0;int zeroCount = 0;  // 記錄窗口內0的數量int maxLen = 0;     // 記錄最大連續1的長度while (right < n) {// 擴展窗口：如果當前元素是0，增加zeroCountif (nums[right] == 0) {zeroCount++;}// 收縮窗口：如果窗口內0的數量超過kwhile (zeroCount > k) {if (nums[left] == 0) {zeroCount--;}left++;}// 更新最大長度maxLen = max(maxLen, right - left + 1);right++;}return maxLen;}
};

復雜度分析

• 時間復雜度：O(n)，其中 n 是數組的長度。每個元素最多被訪問兩次（右指針和左指針各一次）。
• 空間復雜度：O(1)，只需要常數級的額外空間。

關鍵點解釋

1. 窗口合法性：窗口內 0 的數量 ≤ k 時，窗口合法，可以計算長度。
2. 動態調整：通過移動左指針 left，動態調整窗口大小，確保窗口內 0 的數量始終合法。
3. 最大長度更新：每次窗口合法時，計算當前窗口長度 right - left + 1，并更新最大值。

這種滑動窗口的思想在處理數組中的子數組問題時非常常見，尤其是需要滿足特定條件的最長/最短子數組問題。