Skip to content

Lesson 14 列表双指针算法

目录

1 对撞指针

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

对撞指针

1.1 对撞指针求解步骤

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

1.2 对撞指针伪代码模板

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
left, right = 0, len(nums) - 1

while left < right:
    if 满足要求的特殊条件:
        return 符合条件的值 
    elif 一定条件 1:
        left += 1
    elif 一定条件 2:
        right -= 1

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]。

参考解答

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left = 0
        right = len(numbers) - 1
        while left < right:
            total = numbers[left] + numbers[right]
            if total == target:
                return [left + 1, right + 1]
            elif total < target:
                left += 1
            else:
                right -= 1
        return [-1, -1]

1.5 举一反三

1.5.1 LC11 盛水最多的容器

问题描述

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

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

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

说明： 你不能倾斜容器。

示例：

Python
1
2
3
输入：[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，跳出循环，最后返回最大的面积。

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

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

为什么是这样？

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

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

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

参考解答

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def maxArea(self, height: List[int]) -> int:
        left = 0
        right = len(height) - 1
        ans = 0
        while left < right:
            area = min(height[left], height[right]) * (right-left)
            ans = max(ans, area)
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        return ans

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，并返回答案。

参考解答

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort()
        size = len(people)
        left, right = 0, size - 1
        ans = 0
        while left < right:
            if people[left] + people[right] > limit:
                right -= 1
            else:
                left += 1
                right -= 1
            ans += 1
        if left == right:
            ans += 1
        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的元素。

参考解答

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        left, right = 0, len(arr) - 1

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

        # 返回从 left 到 right 的 k 个元素
        return arr[left:left + k]

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.append(nums[right])。
  3. 当窗口达到 window_size 大小时，即满足 right - left + 1 >= window_size 时，判断窗口内的连续元素是否满足题目限定的条件：
  4. 如果满足，再根据要求更新最优解。
  5. 然后向右移动 left，从而缩小窗口长度，即 left += 1，使得窗口大小始终保持为 window_size。
  6. 向右移动 right，将元素填入窗口中，即 window.append(nums[right])。
  7. 重复第 2 步到第 4 步，直到 right 到达数组末尾。

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

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
left = 0
right = 0

while right < len(nums):
    window.append(nums[right])

    # 超过窗口大小时，缩小窗口，维护窗口中始终为 window_size 的长度
    if right - left + 1 >= window_size:
        # ... 
        window.pop(0)
        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 += 1，使得窗口大小始终保持为k。
  7. 重复 3~4 步，直到right到达数组末尾。
  8. 最后输出答案数目。

参考解答

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        left = 0
        right = 0
        window_sum = 0
        ans = 0

        while right < len(arr):
            window_sum += arr[right]

            if right - left + 1 >= k:
                if window_sum >= k * threshold:
                    ans += 1
                window_sum -= arr[left]
                left += 1

            right += 1

        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 += 1，使得窗口大小始终保持小于minutes。

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

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

参考解答

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:
        left = 0
        right = 0
        window_count = 0
        ans = 0

        while right < len(customers):
            if grumpy[right] == 1:
                window_count += customers[right]

            if right - left + 1 > minutes:
                if grumpy[left] == 1:
                    window_count -= customers[left]
                left += 1

            right += 1
            ans = max(ans, window_count)

        for i in range(len(customers)):
            if grumpy[i] == 0:
                ans += customers[i]
        return ans

2.3.2 LC239 滑动窗口的最大值

问题描述

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

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

示例 ：

Text Only
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
输入：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当中。

参考解答

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:

        n = len(nums)
        result = []
        window = []  # 用来存储当前窗口中的元素索引

        for i in range(n):
            # 移除窗口中不在范围内的元素（超出窗口大小k的）
            if len(window) > 0 and window[0] <= i - k:
                window.pop(0)

            # 移除窗口中所有小于当前元素的元素
            while len(window) > 0 and nums[window[-1]] <= nums[i]:
                window.pop()

            # 将当前元素索引添加到窗口
            window.append(i)
            # 上面三行通过从后往前pop所有小于等于num[i]来保证当前window递增

            # 当窗口的大小达到k时，记录窗口的最大值
            if i >= k - 1:
                result.append(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 个元素。
  • 虽然 window 列表的长度不一定等于 k，但我们始终只关心当前窗口的 k 个元素中哪个是最大值。
3. window 列表和实际窗口不同：
  • window 列表：它只是用来存储可能成为当前窗口最大值的索引，因此它的长度是动态的。
  • 实际滑动窗口：逻辑上，窗口总是固定大小的，包含 k 个元素。我们只是通过 window 列表高效地找到当前窗口的最大值，而不是实际存储所有窗口中的元素。

关键点：

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

2.3.3 LC643 子数组最大平均数

问题描述

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

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

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

思路分析

1，初始变量定义：

  • 用ans变量维持子数组的最大平均数，初始值为负无穷，即float('-inf')。
  • 用window_total来维持窗口中元素的和。

2.初始化指针：

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

3.向右移动right指针：

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

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

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

5.向右移动left指针：

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

6.重复步骤 4 到 5：

  • 直到right到达数组末尾。

7.输出结果：

  • 最后输出答案ans。

参考解答

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        left = 0
        right = 0
        window_total = 0
        ans = float('-inf')
        while right < len(nums):
            window_total += nums[right]

            if right - left + 1 >= k:
                ans = max(window_total / k, ans)
                window_total -= nums[left]
                left += 1

            # 向右侧增大窗口
            right += 1

        return ans

2.4 不定长度滑动窗口

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

不定长度滑动窗口

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

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

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

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
left = 0
right = 0

while right < len(nums):
    window.append(nums[right])

    while 窗口需要缩小:
        # ... 可维护答案
        window.pop(0)
        left += 1

    # 向右侧增大窗口
    right += 1

2.5 不定窗口例题讲解

2.5.1 LC209 长度最小的子数组

问题描述

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

找出该数组中满足其总和大于等于target的长度最小的

子数组

[numsl, numsl+1, ..., numsr-1, numsr]，并返回其长度。如果不存在符合条件的子数组，返回0。

思路分析

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

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

参考解答

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        size = len(nums)
        ans = size + 1
        left = 0
        right = 0
        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 += 1

            right += 1

        return ans if ans != size + 1 else 0

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. 记录累积答案个数加1，继续右移right，直到 right > len(nums) 结束。
  6. 输出累积答案个数。

参考解答

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        if k <= 1:
            return 0

        size = len(nums)
        left = 0
        right = 0
        window_product = 1

        count = 0

        while right < size:
            window_product *= nums[right]

            while window_product >= k:
                window_product /= nums[left]
                left += 1

            count += (right - left + 1)
            right += 1

        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 len(s) - left，也就是符合条件的最多次重复字符。

参考解答

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        max_count = 0  # 当前窗口中出现次数最多的字符的次数
        left = 0  # 窗口的左边界
        counts = [0] * 26  # 用于统计窗口中各字符的出现次数，索引对应'A'-'Z'

        for right in range(len(s)):
            index = ord(s[right]) - ord('A')  # 将字符转换为0-25的索引
            counts[index] += 1  # 增加当前字符的计数
            max_count = max(max_count, counts[index])  # 更新最大出现次数

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

        return len(s) - 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.计算结果

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

参考代码

Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        target = sum(nums) - x
        size = len(nums)
        if target < 0:
            return -1
        if target == 0:
            return size
        left, right = 0, 0
        window_sum = 0
        max_len = float('-inf')

        while right < size:
            window_sum += nums[right]

            while window_sum > target:
                window_sum -= nums[left]
                left += 1
            if window_sum == target:
                max_len = max(max_len, right - left + 1)
            right += 1
        return len(nums) - max_len if max_len != float('-inf') else -1

3 课后练习

对撞指针

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

固定长度滑动窗口

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

不定长度滑动窗口

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