一、題目鏈接

最大連續1的個數 Ⅲ

二、題目

三、題目解析

注意題目中說的是最多k次，在一個數組翻轉次數是可以 ≤ k的。

四、算法原理

因為翻轉操作太復雜，無需翻轉。所以可以把本題同等轉化為：找0的個數不超過k的最長子數組。

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

暴力枚舉出所有0的個數不超過k的子數組，并用變量zero記錄0的個數，時刻更新最長長度。

---

模擬暴力解法的過程，進而發現優化的地方：

right所指為1，zero不統計，right++
right所指為0，zero+=1，right++

接下來left++，right回退，開始枚舉以第二個數開始的符合要求的子數組。發現right停在了一樣的位置，再分析發現在藍色區間內開始枚舉的話，right一定會在一樣的位置停下，并且zero還會超過限定次數：

綜上得出規律1：找到一個結果后，right不用回退，left跳過這一區間。 此時zero為2，right再接著向右枚舉。規律2：left向右移動結束后，right繼續向右移動。—— 同向雙指針

解法二：滑動窗口

五、編寫代碼

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

六、時空復雜度

時間復雜度：O(n)
空間復雜度：O(1)