5.5 滑动窗口 / 双指针

5.5.1 满足条件的最长子串

例题：力扣 1004. 最大连续1的个数 III

给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 。

返回仅包含 1 的最长（连续）子数组的长度。

示例 1： 输入：A = [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： 输入：A = [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。

提示：

1 <= A.length <= 20000
0 <= K <= A.length
A[i] 为 0 或 1

如果使用暴力枚举的做法，需要枚举每一个子数组，即

// 枚举左右端点
for (int i=0; i<n; ++i) {
    for (int j=i; j<n; ++j) {
        // 当前子数组为 a[i:j]
    }
}
// 或先枚举长度，再枚举起点
for (int len=1; len<=n; ++len) {
    for (int i=0; i+len-1<n; ++i) {
        // 当前子数组为 a[i:i+len-1]
    }
}

在枚举子数组这一步的时间复杂度为 #card=math&code=O%28n%5E2%29&id=SUk8w)。如何优化呢？

由于我们需要找到的答案是满足条件的、最长的数组 ，当我们每找到一个满足条件的子数组，它的长度一定小于等于答案数组的长度。于是，我们在枚举时，可以如下操作，从最小长度开始枚举数组，仅当符合条件时增加数组长度：

for (int l=0, r=0; r<n; ++r) {
    if (!check()) {    // 不满足条件时，长度不增加
        ++l;
    }
}

如上，在 for 语句初始化两个指针，是一种常规写法。你也可以使用 while 循环：

int l = 0, r = 0;
while (r < n) {
    if (!check()) {
        ++l;
    }
    ++r;
}

这种算法的精髓在于，指针不走回头路，两根指针分别最多前进 次，且保证不会漏掉答案。

参考代码

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int n = nums.size();
        int cnt0 = 0;                // 滑动窗口中 0 的数量
        int ans = 0;
        for (int l=0, r=0; r<n; ++r) {
            if (nums[r] == 0) {        // 更新 0 的数量
                ++cnt0;
            }
            if (cnt0 > k) {            // 不满足条件时，长度不增加
                if (nums[l] == 0) { // 更新 0 的数量
                    --cnt0;
                }
                ++l;
            }
            ans = max(ans, r - l + 1);
        }
        return ans;
    }
};

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int n = nums.size();
        int cnt0 = 0;
        int l = 0, r = 0;
        while (r < n) {
            if (nums[r] == 0) {
                ++cnt0;
            }
            if (cnt0 > k) {
                if (nums[l] == 0) {
                    --cnt0;
                }
                ++l;
            }
            ++r;
        }
        return r - l;        // 与上一个版本区别是多执行一次 ++r;因此r-l就是长度
    }
};

时间复杂度：#card=math&code=O%28n%29&id=nQMqb)

5.5.2 对撞双指针

例题：力扣 633. 平方数之和

题解：官方题解 - 双指针解法

正确性：为什么双指针不会错过正确答案？双指针的本质。

左右指针分别从两端出发，相遇为止，且保证不会漏掉正确答案的扫描。

for (int i=0; j=n-1; i<=j; ) {
    // 根据具体题意 ++i, --j
}

时间复杂度同样是 #card=math&code=O%28n%29&id=ECHjl)