Lesson 14 列表双指针算法

目录

• 1 对撞指针
  • 1.1 对撞指针求解步骤
  • 1.2 对撞指针伪代码模板
  • 1.3 对撞指针适用范围
  • 1.4 例题讲解
    • 1.4.1 LC167 两数之和II - 输入有序数组
  • 1.5 举一反三
    • 1.5.1 LC11 盛水最多的容器
    • 1.5.2 LC881 救生艇
    • 1.5.3 LC658 找到K个最接近的元素
• 2 滑动窗口
  • 2.1 固定长度滑动窗口
  • 2.2 固定窗口例题讲解
    • 2.2.1 LC1343 大小为 K 且平均值大于等于阈值的子数组数目
  • 2.3 固定窗口举一反三
    • 2.3.1 LC1052 爱生气的书店老板
    • 2.3.2 LC239 滑动窗口的最大值
    • 2.3.3 LC643 子数组最大平均数
  • 2.4 不定长度滑动窗口
  • 2.5 不定窗口例题讲解
    • 2.5.1 LC209 长度最小的子数组
  • 2.6 不定窗口举一反三
    • 2.6.1 LC713 乘积小于K的子数组
    • 2.6.2 LC424 替换后的最长重复字符
    • 2.6.3 LC1658 将x减到0的最小操作数
• 3 课后练习
  • 对撞指针
  • 固定长度滑动窗口
  • 不定长度滑动窗口

1 对撞指针

对撞指针：指的是两个指针 left 和 right 分别指向序列的第一个元素和最后一个元素，然后 left 指针不断递增，right 指针不断递减，直到两个指针相遇（即 left == right），或者满足其他要求的特殊条件为止。

1.1 对撞指针求解步骤

1. 使用两个指针 left , right。left 指向序列第一个元素，即：left = 0 , right 指向序列最后一个元素，即：nums.size() - 1。
2. 在循环体中将左右指针相向移动，当满足一定条件时，将左指针右移, left++。当满足另外一定条件时，将右指针左移, right-- 。
3. 直到两指针相撞（即 left == right ），或者满足其他要求的特殊条件时，跳出循环体。

1.2 对撞指针伪代码模板

int left = 0, right = nums.size() - 1;

while (left < right) {
    if (满足要求的特殊条件) {
        return 符合条件的值;
    } else if (一定条件1) {
        left++;  // 移动左指针
    } else if (一定条件2) {
        right--;  // 移动右指针
    }
}
return 没找到 或 找到对应值;

1.3 对撞指针适用范围

对撞指针一般用来解决有序数组或者字符串问题：

• 查找有序数组中满足某些约束条件的一组元素问题：比如二分查找、数字之和等问题。
• 字符串反转问题：反转字符串、回文数、颠倒二进制等问题。

1.4 例题讲解

1.4.1 LC167 两数之和II - 输入有序数组

问题描述

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

思路分析

可以考虑使用对撞指针来减少时间复杂度。具体做法如下：

1. 使用两个指针 left 和 right。left 指向数组中值最小的元素位置，right 指向数组中值最大的元素位置。
2. 判断这两个位置上元素的和与目标值之间的关系：
3. 如果元素和等于目标值，则返回这两个元素的位置。
4. 如果元素和大于目标值，则将 right 向左移动，继续检测。
5. 如果元素和小于目标值，则将 left 向右移动，继续检测。
6. 继续移动 left 和 right，直到它们相遇停止检测。
7. 如果最终没有找到符合条件的两个数，则返回 [-1, -1]。

参考解答

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int left = 0;
        int right = numbers.size() - 1;

        while (left < right) {
            int total = numbers[left] + numbers[right];

            if (total == target) {
                // 返回的是下标从1开始，所以需要+1
                return {left + 1, right + 1};
            } 
            else if (total < target) {
                left++;  // 总和小于目标值，左指针右移
            } 
            else {
                right--;  // 总和大于目标值，右指针左移
            }
        }

        return {-1, -1};  // 没有找到结果
    }
};

1.5 举一反三

1.5.1 LC11 盛水最多的容器

问题描述

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明： 你不能倾斜容器。

示例：

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

思路分析

从示例中可以看出，如果确定好左右两端的直线，容纳的水量是由「左右两端直线中较低直线的高度 * 两端直线之间的距离」所决定的。所以我们应该使得「左右两端的直线尽量高且距离尽可能远」，这样才能使盛水面积尽可能的大。

可以使用对撞指针求解。移动较低直线所在的指针位置，从而得到不同的高度和面积，最终获取其中最大的面积。具体做法如下：

1. 使用两个指针 left 和 right。left 指向数组的起始位置，right 指向数组的末尾位置。
2. 计算由 left 和 right 构成的容器面积，同时维护并更新最大面积值。
3. 比较 left 和 right 所对应的高度：
4. 如果 left 指向的高度较低，则将 left 指针右移

5. 如果 right 指向的高度较低，则将 right 指针左移

6. 如果遇到left == right，跳出循环，最后返回最大的面积。

这里其实用到了贪心的思想，因为在每一步中，我们总是基于当前的局部最优解作出选择。

在本题中所说的局部最优解为“每次向里移动更短的那一条边“就是我们所说的局部最优解。

为什么是这样？

首先假设我们移动的是两边中更长的那一条边，那么移动之后底边的距离是一定缩短的，而长的一边（如上图为右边红色）的长度不管是变长还是变短，由于木桶短板效应，最终要乘的高度都不可能大于短的一边（如上图左边红色）的高，所以得到的新容器的容积一定是小于原容器的。

那既然移动长的得到容积一定更小，那想要得到容积变大的可能只能是移动更短的那一边，才有可能实现。

而通过对撞指针，刚好可以通过收窄两边的指针来寻找最优解，且从左右两边开始，过程中记录最值，可以保证没有漏掉最优解。

参考解答

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0;
        int right = height.size() - 1;
        int maxArea = 0;

        while (left < right) {
            // 计算当前容器的面积
            int area = min(height[left], height[right]) * (right - left);
            // 更新最大面积
            maxArea = max(maxArea, area);

            // 移动指针，选择较小高度的那一边
            if (height[left] < height[right]) {
                left++;  // 左边较低，左指针右移
            } else {
                right--;  // 右边较低，右指针左移
            }
        }

        return maxArea;
    }
};

1.5.2 LC881 救生艇

问题描述

给定数组 people 。people[i]表示第 i 个人的体重 ，船的数量不限，每艘船可以承载的最大重量为 limit。

每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。

返回 承载所有人所需的最小船数 。

思路分析

我们也可以利用贪心算法的思想，让最重的和最轻的人一起走。这样一只船就可以尽可能的带上两个人。

具体做法如下：

1. 先对数组进行升序排序，使用变量 ans 记录所需最小船只数量。

2. 使用两个指针，left 和 right：

3. left 指向数组的开始位置。

4. right 指向数组的结束位置。

5. 判断 people[left] 和 people[right] 之和：

6. 如果 people[left] + people[right] > limit，则让重的人（right）上船，船数量加 1，并令 right 左移，继续判断。

7. 如果 people[left] + people[right] <= limit，则两个人都可以上船，船数量加 1，并令 left 右移，right 左移，继续判断。

8. 如果 left == right，则让最后一个人上船，船数量加 1，并返回答案。

参考解答

class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        // 先对数组进行升序排序
        sort(people.begin(), people.end());
        int left = 0, right = people.size() - 1;
        int ans = 0;

        // 使用双指针进行贪心操作
        while (left <= right) {
            if (people[left] + people[right] <= limit) {
                // 如果最轻和最重的人能一起上船，则一起上
                left++;
            }
            // 不管能不能一起上，最重的人都要上船
            right--;
            ans++;
        }

        return ans;
    }
};

1.5.3 LC658 找到K个最接近的元素

问题描述

给定一个 排序好 的数组arr，两个整数k和x，从数组中找到最靠近x（两数之差最小）的k个数。返回的结果必须要是按升序排好的。

整数a比整数b更接近x需要满足：

• |a - x| < |b - x|或者
• |a - x| == |b - x|且a < b

思路分析

1.初始化指针

• 左指针left指向数组的开头（索引0）。
• 右指针right指向数组的末尾（索引n-1）。

2.移动指针

我们希望最终找到一段长度为k的子数组，其中元素距离x最接近。因此，在移动过程中要对比arr[left]和arr[right]与x的距离：

• 如果arr[left]与x的距离大于arr[right]与x的距离，说明右边的元素更接近x，因此应移动左指针left++，缩小左侧的搜索空间。
• 如果arr[right]与x的距离更远，说明左边的元素更接近x，因此应移动右指针right--，缩小右侧的搜索空间。

3.停止条件

当窗口中剩下的元素数量刚好为k时，停止移动指针，此时窗口中的元素就是我们要找的k个最接近x的元素。

参考解答

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        int left = 0, right = arr.size() - 1;

        // 当区间长度大于 k 时，不断移动指针
        while (right - left >= k) {
            // 比较两端的距离，移动较远的一端
            if (abs(arr[left] - x) > abs(arr[right] - x)) {
                left++;
            } else {
                right--;
            }
        }

        // 创建一个新的 vector 来存储结果
        vector<int> result;

        // 将从 arr[left] 到 arr[left + k] 的元素添加到 result 中
        for (int i = left; i < left + k; ++i) {
            result.push_back(arr[i]);
        }

        // 返回结果
        return result;
    }
};

2 滑动窗口

在计算机网络中，滑动窗口协议（Sliding Window Protocol）是传输层进行流控的一种措施，接收方通过通告发送方自己的窗口大小，从而控制发送方的发送速度，从而达到防止发送方发送速度过快而导致自己被淹没的目的。我们所要讲解的滑动窗口算法也是利用了同样的特性。

滑动窗口算法（Sliding Window）：在给定数组 / 字符串上维护一个固定长度或不定长度的窗口。可以对窗口进行滑动操作、缩放操作，以及维护最优解操作。

• 滑动操作：窗口可按照一定方向进行移动。最常见的是向右侧移动。
• 缩放操作：对于不定长度的窗口，可以从左侧缩小窗口长度，也可以从右侧增大窗口长度。

滑动窗口利用了双指针中的快慢指针技巧，我们可以将滑动窗口看做是快慢指针两个指针中间的区间，也可以将滑动窗口看做是快慢指针的一种特殊形式。

滑动窗口适用范围

滑动窗口算法一般用来解决一些查找满足一定条件的连续区间的性质（长度等）的问题。该算法可以将一部分问题中的嵌套循环转变为一个单循环，因此它可以减少时间复杂度。

按照窗口长度的固定情况，我们可以将滑动窗口题目分为以下两种：

• 固定长度窗口：窗口大小是固定的。
• 不定长度窗口：窗口大小是不固定的。
• 求解最大的满足条件的窗口。
• 求解最小的满足条件的窗口。

2.1 固定长度滑动窗口

固定长度滑动窗口算法（Fixed Length Sliding Window）：在给定数组 / 字符串上维护一个固定长度的窗口。可以对窗口进行滑动操作、缩放操作，以及维护最优解操作。

固定长度滑动窗口算法步骤

假设窗口的固定大小为 window_size。

1. 使用两个指针 left 和 right。初始时，left 和 right 都指向序列的第一个元素，即：left = 0，right = 0，区间 [left, right] 被称为一个「窗口」。
2. 当窗口未达到 window_size 大小时，不断移动 right，先将数组前 window_size 个元素填入窗口中，即 window.push_back(nums[right])。
3. 当窗口达到 window_size 大小时，即满足 right - left + 1 >= window_size 时，判断窗口内的连续元素是否满足题目限定的条件：
   1. 如果满足，再根据要求更新最优解。
   2. 然后向右移动 left，从而缩小窗口长度，即 left += 1，使得窗口大小始终保持为 window_size。
4. 向右移动 right，将元素填入窗口中，即 window.push_back(nums[right])。
5. 重复第 2 步到第 4 步，直到 right 到达数组末尾。

固定长度滑动窗口代码模板

int left = 0;
int right = 0;

while (right < nums.size()) {
    window.push_back(nums[right]);

    // 超过窗口大小时，缩小窗口，维护窗口中始终为 window_size 的长度
    if ((right - left + 1) >= window_size) {
        // ... 维护答案
        window.erase(window.begin());
        left += 1;
    }
    // 向右侧增大窗口
    right += 1;
}

2.2 例题讲解

2.2.1 LC1343 大小为 K 且平均值大于等于阈值的子数组数目

问题描述

给你一个整数数组 arr 和两个整数 k 和 threshold 。

请你返回长度为 k 且平均值大于等于 threshold 的子数组数目。

思路分析

这道题目是典型的固定窗口大小的滑动窗口题目。窗口大小为k。具体做法如下：

1. ans用来维护答案数目。 window_sum用来维护窗口中元素的和。
2. left、 right都指向序列的第一个元素，即：left = 0,right = 0。
3. 向右移动right，先将k个元素填入窗口中，即 window_sum += arr[right] 。
4. 当窗口元素个数为k时，即满足right - left + 1 >= k时，判断窗口内的元素和平均值是否大于等于阈值threshold。
5. 如果满足，则答案数目加1。
6. 然后向右移动left，从而缩小窗口长度，即left++，使得窗口大小始终保持为k。
7. 重复 3 ~ 4 步，直到right到达数组末尾。
8. 最后输出答案数目。

参考解答

class Solution {
public:
    int numOfSubarrays(std::vector<int>& arr, int k, int threshold) {
        int left = 0;
        int right = 0;
        int window_sum = 0;
        int ans = 0;
        int n = arr.size();

        // 滑动窗口遍历数组
        while (right < n) {
            window_sum += arr[right];  // 加入右侧元素

            // 当窗口大小达到 k 时，进行判断
            if (right - left + 1 >= k) {
                // 如果窗口内的平均值大于等于 threshold
                if (window_sum >= k * threshold) {
                    ans++;  // 满足条件，答案加 1
                }
                // 缩小窗口，移除左侧元素
                window_sum -= arr[left];
                left++;
            }

            right++;  // 右指针移动，扩大窗口
        }

        return ans;
    }
};

2.3 举一反三

2.3.1 LC1052 爱生气的书店老板

问题描述

有一个书店老板，他的书店开了 n 分钟。每分钟都有一些顾客进入这家商店。给定一个长度为 n 的整数数组 customers ，其中 customers[i] 是在第 i 分钟开始时进入商店的顾客数量，所有这些顾客在第 i 分钟结束后离开。

在某些分钟内，书店老板会生气。 如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。

当书店老板生气时，那一分钟的顾客就会不满意，若老板不生气则顾客是满意的。

书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 minutes 分钟不生气，但却只能使用一次。

请你返回 这一天营业下来，最多有多少客户能够感到满意 。

思路分析

这是一个固定长度的滑动窗口问题。我们可以维护一个窗口大小为 minutes 的滑动窗口。使用 window_count 记录当前窗口内生气的顾客人数。然后滑动求出窗口中最多的顾客数，最后累加上老板未生气时的顾客数，就是答案。具体做法如下：

1. 用 ans 来维护答案数目。window_count 用来维护窗口中生气的顾客人数。

2. left 和 right 都指向序列的第一个元素，即：left = 0，right = 0。

3. 如果书店老板生气，则将这一分钟的顾客数量加入到 window_count 中，然后向右移动 right。

4. 当窗口元素个数大于 minutes 时，即：right - left + 1 > count 时，如果最左边界老板处于生气状态，则向右移动 left，从而缩小窗口长度，即 left++，使得窗口大小始终保持小于 minutes。

5. 重复步骤 3～4，直到 right 到达数组末尾。

6. 最后累加上老板未生气时的顾客数，最后输出答案。

参考解答

class Solution {
public:
    int maxSatisfied(std::vector<int>& customers, vector<int>& grumpy, int minutes) {
        int left = 0, right = 0;
        int window_count = 0, ans = 0;
        int n = customers.size();

        // 滑动窗口求解不满意情况下能够改善的顾客人数
        while (right < n) {
            if (grumpy[right] == 1) {
                window_count += customers[right];  // 老板生气时，把顾客加入窗口
            }

            // 当窗口大小超过 minutes，缩小窗口
            if (right - left + 1 > minutes) {
                if (grumpy[left] == 1) {
                    window_count -= customers[left];  // 移除窗口左端的顾客
                }
                left++;
            }

            ans = max(ans, window_count);  // 记录最大窗口内的顾客数量
            right++;
        }

        // 计算老板不生气时的顾客人数
        for (int i = 0; i < n; ++i) {
            if (grumpy[i] == 0) {
                ans += customers[i];  // 老板不生气时，这些顾客一直是满意的
            }
        }

        return ans;
    }
};

2.3.2 LC239 滑动窗口的最大值

问题描述

给你一个整数数组nums，有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的k个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例 ：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

思路分析

使用索引而不是值： 我们使用 window 列表来存储数组中元素的索引，而不是直接存储元素值。通过这些索引，我们可以快速访问到数组中的元素值。

保持 window 中的元素递减顺序： 为了确保每次窗口滑动时都能快速得到最大值，我们在 window 中保存的索引对应的元素值是递减的。也就是说，window 中第一个元素（window[0]）对应的数组值总是当前窗口的最大值。

每次新元素进入窗口时：

• 移除超出范围的元素索引： 如果窗口最左边的元素已经不在当前窗口范围内（超出了窗口的大小 k），我们就把它从 window 里移除。
• 移除比当前元素小的索引： 如果当前元素比 window 中最后一个索引对应的元素值大，那么我们就把这些较小的元素索引移除，因为它们不可能再成为窗口中的最大值了。

举例分析

假设 nums = [1, 3, -1, -3, 5, 3, 6, 7]，k = 3，即窗口大小为 3。

1. 开始时，我们遍历数组，遇到 1，把它的索引 0 放入 window。
   • window = [0]，最大值是 1。
2. 遇到 3 时，3 比 1 大，所以我们移除 1 的索引 0，然后把 3 的索引 1 放入 window。
   • window = [1]，最大值是 3。
3. 遇到 -1 时，-1 小于 3，我们直接把 -1 的索引 2 放入 window，此时最大值仍然是 3。
   • window = [1, 2]，最大值是 3。
4. 窗口向右滑动，当我们进入下一个元素时，如果 window 里的第一个索引已经超出了窗口的范围（即索引小于 i - k），我们就把它移除，确保 window[0] 总是当前窗口内的索引。

可能会有迷惑的地方是：window 里面的元素数量 不一定等于 k；window 中存储的是滑动窗口内的元素索引，而且我们通过两个关键操作来确保它的正确性：

1. 移除超出当前窗口范围的元素：window 中的第一个索引如果超出窗口范围（即已经不属于当前窗口的 k 个元素），就会被移除。
2. 保持单调递减顺序：我们移除 window 里比当前元素小的元素索引，所以 window 里可能并不包含完整的 k个元素。

最后因为我们window[0]永远是当前滑动区间的最大索引值，每次滑动添加nums[window[0]]到result当中。

参考解答

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> window; // 用来存储当前窗口中的元素索引
        vector<int> result; // 用于存储结果的数组

        for (int i = 0; i < n; i++) {
            // 移除窗口中不在范围内的元素（超出窗口大小k的）
            if (!window.empty() && window[0] <= i - k) {
                window.erase(window.begin());
            }

            // 移除窗口中所有小于当前元素的元素
            while (!window.empty() && nums[window.back()] <= nums[i]) {
                window.pop_back();
            }

            // 将当前元素索引添加到窗口
            window.push_back(i);

            // 当窗口的大小达到k时，记录窗口的最大值
            if (i >= k - 1) {
                result.push_back(nums[window[0]]);  // 窗口的第一个元素是最大值的索引
            }
        }

        return result;
    }
};

关键解释

window 的长度不同于 k，但仍然属于固定滑动窗口。

1. 窗口的大小是固定的：

无论 window 列表中的元素个数是多少，我们在逻辑上始终处理一个大小为 k 的窗口。即便 window 列表中存储的索引数量可能少于 k，我们每次移动窗口时，都保证窗口覆盖数组的 k 个连续元素。

2. 窗口的范围是固定的：

每次处理新元素时，窗口总是包含 k 个连续的元素。例如，如果窗口大小 k=3，当遍历到第 i 个元素时，窗口对应的是 nums[i-(k-1)] 到 nums[i] 这 k 个元素。

3. window 列表和实际窗口不同：

• window 列表：它只是用来存储可能成为当前窗口最大值的索引，因此它的长度是动态的。
• 实际滑动窗口：逻辑上，窗口总是固定大小的，包含 k 个元素。我们只是通过 window 列表高效地找到当前窗口的最大值，而不是实际存储所有窗口中的元素。

关键点：

• 固定滑动窗口：窗口的大小始终是 k，每次只滑动一格。
• window 列表长度不等于窗口大小：window 列表只存储与计算最大值相关的索引，因此长度可能小于 k。

2.3.3 LC643 子数组最大平均数

问题描述

给你一个由n个元素组成的整数数组nums和一个整数k。

请你找出平均数最大且 长度为k 的连续子数组，并输出该最大平均数。

任何误差小于10^-5的答案都将被视为正确答案。

思路分析

1. 初始变量定义：

   • 用ans变量维护子数组的最大平均数，初始值为负无穷，即-DBL_MAX（C++ 中的负无穷）。
   • 用window_total来维持窗口中元素的和。

2. 初始化指针：

   • left和right都指向数组的第一个元素，即：left = 0，right = 0。

3. 向右移动right指针：

   • 将k个元素填入窗口中。

4. 窗口元素数量为k时：

   • 当right - left + 1 >= k时，计算窗口内的元素和，并维护子数组的最大平均数。

5. 向右移动left指针：

   • 从而缩小窗口长度，即left++，使得窗口大小始终保持为k。

6. 重复步骤 4 到 5：

   • 直到right到达数组末尾。

7. 输出结果：

   • 最后输出答案ans。

参考解答

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        int left = 0, right = 0;
        double window_total = 0, ans = -DBL_MAX;

        while (right < nums.size()) {
            window_total += nums[right];

            // 窗口内元素数量达到 k 时，计算窗口平均值并更新最大平均值
            if (right - left + 1 >= k) {
                ans = max(window_total / k, ans);
                window_total -= nums[left]; // 移动左指针，缩小窗口
                left++;
            }

            // 向右侧增大窗口
            right++;
        }

        return ans;
    }
};

2.4 不定长度滑动窗口

不定长度滑动窗口算法（Sliding Window）：在给定数组 / 字符串上维护一个不定长度的窗口。可以对窗口进行滑动操作、缩放操作，以及维护最优解操作。

不定长度滑动窗口算法步骤

1. 使用两个指针 left、right。初始时，left 和 right 都指向序列的第一个元素。即：left = 0, right = 0，区间 [left, right] 被称为一个「窗口」。
2. 将区间最右侧元素添加入窗口中，即 window.push_back(nums[right])。
3. 然后向右移动 right，从而增大窗口长度，即 right += 1。直到窗口中的连续元素满足要求。
4. 此时，停止增加窗口大小，转向不断将左侧元素移出窗口，即 window.erase(window.begin())。
5. 然后向右移动 left，从而缩小窗口长度，即 left += 1，直到窗口中的连续元素不再满足要求。
6. 重复第 2 步到第 5 步，直到 right 到达序列末尾。

不定长度滑动窗口代码模板

int left = 0;
int right = 0;

while(right < nums.size()) {
    window.push_back(nums[right]);

    while (窗口需要缩小) {
        // 可维护答案
        window.erase(window.begin()); 
        left += 1;
    }

    // 向右侧增大窗口
    right += 1;
}

2.5 例题讲解

2.5.1 LC209 长度最小的子数组

问题描述

给定一个含有n个正整数的数组和一个正整数target。

找出该数组中满足其总和大于等于target的长度最小的子数组: [nums_l, nums_l+1, ..., nums_r-1, nums_r]

并返回其长度。如果不存在符合条件的子数组，返回0。

思路分析

用滑动窗口来记录连续子数组的和，设定两个指针：left、right，分别指向滑动窗口的左右边界，保证窗口中的和刚好大于等于 target。

1. 一开始, left、right 都指向 0。
2. 向右移动 right，将最右侧元素加入当前窗口和 window_sum 中。
3. 如果 window_sum >= target，则不断右移 left，缩小滑动窗口长度，并更新窗口和的最小值，直到 window_sum < target。
4. 然后继续右移 right，直到 right >= nums.size() 结束。
5. 输出窗口和的最小值作为答案。

参考解答

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int size = nums.size();
        int ans = size + 1;  // 初始化一个较大的值，用来记录最小子数组长度
        int left = 0;        // 左指针
        int right = 0;       // 右指针
        int window_sum = 0;  // 滑动窗口的当前和

        // 移动右指针，扩大窗口
        while (right < size) {
            window_sum += nums[right];  // 加入右指针指向的元素

            // 当窗口和大于等于目标值时，开始缩小窗口
            while (window_sum >= target) {
                ans = min(ans, right - left + 1);  // 更新最小子数组长度
                window_sum -= nums[left];          // 移除左指针指向的元素
                left++;                            // 左指针右移，缩小窗口
            }

            right++;  // 右指针右移，继续扩大窗口
        }

        // 如果没有找到符合条件的子数组，返回 0；否则返回最小长度
        return ans == size + 1 ? 0 : ans;
    }
};

2.6 举一反三

2.6.1 LC713 乘积小于K的子数组

问题描述

给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。

思路分析

滑动窗口（不定长度）

1. 设定两个指针：left、right，分别指向滑动窗口的左右边界，保证窗口内所有数的乘积 window_product 都小于 k。使用 window_product 记录窗口中的乘积值，使用 count 记录符合要求的子数组个数。
2. 一开始，left 和 right 都指向 0。
3. 向右移动 right，将最右侧元素加入当前子数组乘积 window_product 中。
4. 如果 window_product >= k，则不断右移 left，缩小滑动窗口长度，并更新当前乘积值 window_product，直到 window_product < k。
5. 每次窗口内符合条件时，累积答案个数加上 right - left + 1，继续右移 right，直到 right >= nums.size() 结束。
6. 输出累积的答案个数。

参考解答

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if (k <= 1) return 0; // 如果 k <= 1，无法找到乘积小于 k 的子数组，直接返回 0

        int size = nums.size();
        int left = 0;        // 左指针
        int right = 0;       // 右指针
        int window_product = 1; // 滑动窗口的当前乘积
        int count = 0;       // 记录符合要求的子数组数量

        // 移动右指针，扩大窗口
        while (right < size) {
            window_product *= nums[right];  // 更新当前窗口的乘积

            // 如果窗口的乘积大于等于 k，则缩小窗口
            while (window_product >= k && left <= right) {
                window_product /= nums[left]; // 从乘积中移除左指针指向的元素
                left++;                       // 左指针右移，缩小窗口
            }

            // 右指针 - 左指针 + 1 表示以 right 结尾的、乘积小于 k 的子数组个数
            count += (right - left + 1);
            right++; // 右指针右移，继续扩大窗口
        }

        return count;
    }
};

2.6.2 LC424 替换后的最长重复字符

问题描述

给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符，并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。 在执行上述操作后，返回 包含相同字母的最长子字符串的长度。

思路分析

1. 使用 counts 数组来统计字母频数。使用 left、right 双指针分别指向滑动窗口的首尾位置，使用 max_count 来维护最长子串的长度。
2. 不断右移 right 指针，增加滑动窗口的长度。
3. 对于当前滑动窗口的子串，如果当前窗口的间距 > 当前出现最大次数的字符的次数 + k 时，意味着替换 k 次仍不能使当前窗口中的字符全变为相同字符，则此时应该将左边界右移，同时将原先左边界的字符频次减少。

具体案例

假设 s = "AABABBA", k = 1。

1. 初始情况：
   • 我们从左边界 left = 0 和右边界 right = 0 开始。
   • max_count = 1，即当前窗口 A 中出现次数最多的字符 A 出现了 1 次。
2. 逐渐扩展窗口：
   • 扩展到 right = 1 时，窗口 AA 中出现最多的字符 A 出现了 2 次，max_count = 2。窗口大小减去 max_count 为 2 - 2 = 0，小于等于 k，所以我们不缩小窗口。
   • 扩展到 right = 2 时，窗口 AAB 中出现最多的字符 A 出现了 2 次，max_count = 2。窗口大小减去 max_count 为 3 - 2 = 1，等于 k，仍然不缩小窗口。
3. 窗口不再满足条件，缩小窗口：
   • 扩展到 right = 4 时，窗口变成 AABAB。此时 A 仍然是出现次数最多的字符，max_count = 2，但窗口大小是 5。5 - 2 = 3，超过了 k = 1。
   • 这时我们必须缩小窗口，将 left 向右移动，移除最左边的 A，这样窗口变成了 ABAB。虽然我们移除了一个 A，max_count 暂时没有变，因为还会有其他字符出现。

4. 继续扩展：

   • 在右边界继续扩展时，max_count 会根据新窗口的字符动态更新，不用担心移除最大频次字符会影响结果。因为此时最大值就是窗口大小值！直到有更多的重复元素出现，也就是更大的窗口值。

5. 返回最大窗口值return s.size() - left，也就是符合条件的最多次重复字符。

参考解答

class Solution {
public:
    int characterReplacement(string s, int k) {
        int max_count = 0;  // 当前窗口中出现次数最多的字符的次数
        int left = 0;  // 窗口的左边界
        vector<int> counts(26, 0);  // 用于统计窗口中各字符的出现次数，大小为26对应'A'-'Z'

        for (int right = 0; right < s.size(); ++right) {
            int index = s[right] - 'A';  // 将字符转换为0-25的索引
            counts[index]++;  // 增加当前字符的计数
            max_count = max(max_count, counts[index]);  // 更新最大出现次数

            // 如果当前窗口大小减去出现最多的字符次数大于k，说明需要缩小窗口
            if ((right - left + 1) - max_count > k) {
                counts[s[left] - 'A']--;  // 移除左边字符的计数
                left++;  // 左边界右移，缩小窗口
            }
        }

        return s.size() - left;  // 返回最大窗口长度
    }
};

2.6.3 LC1658 将x减到0的最小操作数

问题描述

给你一个整数数组nums和一个整数x。每一次操作时，你应当移除数组nums最左边或最右边的元素，然后从x中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。

如果可以将x恰好 减到0，返回 最小操作数 ；否则，返回-1。

思路分析

1.定义目标值

设定 target = sum(nums) - x，意图找到和为 target 的最长连续子数组。

2.初始化变量

• window_sum 用于记录滑动窗口内元素的和。
• max_len 用于跟踪和等于 target 的最长子数组长度。
• left 和 right 初始化为 0，用于标识滑动窗口的边界。

3.滑动窗口操作

• 增加右侧元素：向右移动 right 指针，扩大窗口，更新 window_sum。
• 调整左侧边界：当 window_sum > target 时，逐步右移 left，缩小窗口，直到 window_sum <= target。
• 检查窗口和：如果 window_sum == target，更新 max_len。
• 继续此过程直到 right 越过数组末端。

4.计算结果

输出 nums.size() - max_len，代表需要移除的最少元素数量以达到除了最长和为 target 子数组外的元素。

参考代码

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int target = accumulate(nums.begin(), nums.end(), 0) - x;
        int size = nums.size();

        if (target < 0) return -1; // target 不可能为负数
        if (target == 0) return size; // 如果刚好移除所有元素即可

        int left = 0, right = 0;
        int window_sum = 0, max_len = INT_MIN;

        while (right < size) {
            window_sum += nums[right];

            // 窗口总和大于 target 时缩小窗口
            while (window_sum > target) {
                window_sum -= nums[left];
                left++;
            }

            // 找到窗口总和等于 target 时更新最大子数组长度
            if (window_sum == target) {
                max_len = max(max_len, right - left + 1);
            }

            right++;
        }

        // 如果没找到符合条件的子数组，返回 -1
        return max_len == INT_MIN ? -1 : size - max_len;
    }
};

3 课后练习

对撞指针

题目编号	题目名称	题目描述
15	三数之和	判断整数数组是否存在三元组满足条件。
16	最接近的三数之和	找出数组中三个数之和最接近目标值的组合。
18	四数之和	在数组中找出四个数，使得它们的和等于目标值。
977	有序数的平方	返回非递减顺序的每个数的平方组成的新数组。
611	有效三角形的个数	返回非负整数的数组可以组成三角形三条边的三元组个数。

固定长度滑动窗口

题目编号	题目名称	题目描述
1423	可获得的最大点数	从数组两端选择一定数量的元素，求最大点数。
1456	定长子串中元音的最大数目	找出定长子串中包含最多元音字母的子串。
1151	最少交换次数来组合所有的 1	通过交换位置，将数组中任何位置上的1组合到一起返回所有可能中所需的最少交换次数。
1100	长度为 K 的无重复字符子串	找出所有长度为k且不含重复字符的子串，返回全部满足要求的子串的数目。
567	字符串的排列	判断 s2 是否包含 s1 的排列。

不定长度滑动窗口

题目编号	题目名称	题目描述
1695	删除子数组的最大得分	删除子数组，使得剩余元素的和最大。
795	区间子数组个数	计算满足条件的子数组的数量。
718	最长重复子数组	给两个数组返回公共最长子数组长度。
904	水果成篮	给一个整数数组返回手机水果的最大数目。
1493	删掉一个元素以后全为1的最长子数组	删掉元素的结果数组中，返回最长的且只包含 1 的非空子数组的长度。