练12：双指针

欢迎大家订阅【蓝桥杯Python每日一练】 专栏，开启你的 Python数据结构与算法 学习之旅！

文章目录

• 前言
• 1 同向扫描
• 2 反向扫描
• 3 同向扫描与反向扫描的对比
• 4 例题分析
• • 2.1 回文判定
  • 2.2 美丽的区间
  • 2.3 挑选子串

前言

双指针是一种常用于数组和链表类问题中，指的是用两个指针在问题的输入数据结构中进行遍历。根据应用的场景和指针的运动方向，双指针可以分为同向扫描和反向扫描两种类型。

1 同向扫描

同向扫描指的是两个指针从同一位置或相近的位置开始，向相同的方向移动。常见的应用场景包括：

• 滑动窗口问题：通过一个窗口的左右边界来实现对区间的处理。
• 寻找数组中满足某些条件的子数组。
• 合并两个已排序的数组（例如合并两个有序链表）。

优点：

• 使用双指针的技术可以在 O(n) 时间内完成遍历。
• 避免了暴力搜索的 O(n²) 时间复杂度。

2 反向扫描

反向扫描指的是两个指针从不同的位置开始，分别向相反的方向移动。这种方法通常用于：

• 排序问题：寻找两个数的和等于某个目标值，通常应用于已排序的数组。
• 双端队列问题：需要同时从两端处理数据的场景。
• 快排：快速排序算法通过反向扫描来处理左右子数组的元素。

优点：

• 反向扫描减少了重复计算，快速找到符合条件的解。
• 适用于有序数据结构的情境，利用有序性减少搜索空间。

3 同向扫描与反向扫描的对比

4 例题分析

2.1 回文判定

题目地址：https://www.lanqiao.cn/problems/1371/learning/

样例输入

abcba

样例输出

Y

【示例代码】

s = input()
# 初始化左右指针 l 和 r，l 指向字符串的开始，r 指向字符串的结束
l, r = 0, len(s) - 1 
ok = 'Y' 
# 循环，直到左右指针交错（即 l > r）
while l <= r:  
    # 如果左右指针对应的字符相等
    if s[l] == s[r]:  
        l += 1  # 左指针向右移动
        r -= 1  # 右指针向左移动
    else:  # 如果
        ok = 'N'  
        break 
print(ok)  

【运行结果】

2.2 美丽的区间

题目地址：https://www.lanqiao.cn/problems/1372/learning/

样例输入

5 6
1 2 3 4 5

样例输出

2

【示例代码】

# 读取两个整数 n 和 S。n 是数组的长度，S 是最小和的阈值
n, S = map(int, input().split())  
# 读取一个数组 a，数组的长度是 n，包含 n 个整数
a = list(map(int, input().split()))  

# 初始化左右指针，均指向数组的开始位置
left, right = 0, 0  
# 初始化 tot 变量为 0，用于记录当前区间 [left, right) 的和
tot = 0
# 初始化 min_len 为 n+1（一个大于数组长度的值），用于记录最小子数组长度  
min_len = n + 1  

# 进入循环：通过左指针遍历每个子数组的起始位置
while left < n:
    # 不断拓展右端点，直到子数组的和大于或等于 S
    while right < n and tot < S:
        tot += a[right]  # 将右端点元素加入 tot
        right += 1  # 右端点向右移动

    # 如果当前区间的和满足大于或等于 S
    if tot >= S:
        # 更新最小长度，right - left 是当前区间的长度
        min_len = min(min_len, right - left)  

    # 左端点右移一位，缩小区间，继续寻找下一个合法区间
    # 将左端点元素从 tot 中移除
    tot -= a[left]  
    # 左端点右移
    left += 1  

# 如果没有找到满足条件的子数组，min_len 会保持为 n+1
if min_len == n + 1:
    min_len = 0  # 如果没有找到合法区间，设置 min_len 为 0

# 输出最小子数组长度
print(min_len)

【执行流程】
①初始化

• n = 5，S = 6。
• a = [1, 2, 3, 4, 5]。
• left = 0，right = 0。
• tot = 0，min_len = n + 1 = 6。

②循坏处理

第一轮：left = 0

• 进入 while left < n 循环。
• 内层 while right < n and tot < S 开始：
  • right = 0，tot = 0，tot < S，因此进入循环：
    • tot += a[0] = 0 + 1 = 1，right += 1，right = 1。
  • right = 1，tot = 1，tot < S，继续循环：
    • tot += a[1] = 1 + 2 = 3，right += 1，right = 2。
  • right = 2，tot = 3，tot < S，继续循环：
    • tot += a[2] = 3 + 3 = 6，right += 1，right = 3。
  • right = 3，tot = 6，此时 tot >= S，跳出内层循环。
• tot >= S 时，更新 min_len：
  • min_len = min(min_len, right - left) = min(6, 3 - 0) = 3。
• 然后缩小区间，tot -= a[0] = 6 - 1 = 5，left += 1，left = 1。

第二轮：left = 1

• 进入 while left < n 循环。
• 内层 while right < n and tot < S 继续执行：
  • right = 3，tot = 5，tot < S，继续循环：
    • tot += a[3] = 5 + 4 = 9，right += 1，right = 4。
  • right = 4，tot = 9，此时 tot >= S，跳出内层循环。
• tot >= S 时，更新 min_len：
  • min_len = min(min_len, right - left) = min(3, 4 - 1) = 3。
• 然后缩小区间，tot -= a[1] = 9 - 2 = 7，left += 1，left = 2。

第三轮：left = 2

• 进入 while left < n 循环。
• 内层 while right < n and tot < S 继续执行：
  • right = 4，tot = 7，tot < S，继续循环：
    • tot += a[4] = 7 + 5 = 12，right += 1，right = 5。
  • right = 5，tot = 12，此时 tot >= S，跳出内层循环。
• tot >= S 时，更新 min_len：
  • min_len = min(min_len, right - left) = min(3, 5 - 2) = 3。
• 然后缩小区间，tot -= a[2] = 12 - 3 = 9，left += 1，left = 3。

第四轮：left = 3

• 进入 while left < n 循环。
• 内层 while right < n and tot < S 不再执行，因为 right 已经达到数组的末尾。
• tot >= S 时，更新 min_len：
  • min_len = min(min_len, right - left) = min(3, 5 - 3) = 2。
• 然后缩小区间，tot -= a[3] = 9 - 4 = 5，left += 1，left = 4。

第五轮：left = 4

• 进入 while left < n 循环。
• 内层 while right < n and tot < S 不再执行，因为 right 已经达到数组的末尾。
• 此时，min_len = 2，退出外层循环。

③结果输出
最终 min_len = 2，即最小的子数组长度为 2。

【运行结果】

2.3 挑选子串

题目地址：https://www.lanqiao.cn/problems/1621/learning/

样例输入

7 4 2
4 2 7 7 6 5 1

样例输出

18

【示例代码】

# 读取三个整数 n (数组长度), m (阈值), k (至少有 k 个数 >= m)
n, m, k = map(int, input().split())  
# 读取数组 a，包含 n 个整数
a = list(map(int, input().split()))  
# 初始化左右指针，均指向数组的起始位置
left, right = 0, 0  

ans = 0  # 用来记录满足条件的子数组数量
cnt = 0  # 记录当前窗口中大于等于 m 的元素个数

# 主循环：左指针从0到n遍历数组
while left < n:
    # 内循环：扩展右指针，直到窗口中有至少 k 个元素大于等于 m
    while right < n and cnt < k:
        if a[right] >= m:  # 如果右指针指向的元素大于等于 m
            cnt += 1  # 计数窗口中大于等于 m 的元素数量
        right += 1  # 右指针向右移动，扩大窗口

    # 当窗口中有至少 k 个大于等于 m 的元素时
    if cnt >= k:
        # 计算从 left 到 right-1 的子数组的数量
        # 窗口为 [left, right-1]，[left, right], [left, right+1], ..., [left, n-1]，这些子数组都满足条件
        ans += n - right + 1  # right 已经移动到不满足条件的位置，所有从 left 到 [right, n-1] 的子数组都满足条件

    # 向右移动左指针，缩小窗口，准备进入下一轮
    if a[left] >= m:  # 如果左指针指向的元素大于等于 m
        cnt -= 1  # 移除左边界元素，更新窗口中大于等于 m 的元素数量
    left += 1  # 左指针右移

# 输出满足条件的子数组数量
print(ans)

【执行流程】

①初始化
left = 0, right = 0, cnt = 0, ans = 0

②循坏处理
第一轮外循环 (left = 0)：

• 内循环拓展右指针，直到 cnt >= 2：
  • right = 0: a[right] = 4 >= 4, cnt = 1
  • right = 1: a[right] = 2 < 4, cnt = 1
  • right = 2: a[right] = 7 >= 4, cnt = 2 → 窗口 [0, 2] 满足条件。
• 当前 cnt = 2 >= 2，则有 n - right + 1 = 7 - 3 + 1 = 5 个符合条件的子数组，ans = 5。
• 左指针右移，left = 1，cnt 减少 1。

第二轮外循环 (left = 1)：

• 内循环继续拓展右指针，直到 cnt >= 2：
  • right = 3: a[right] = 7 >= 4, cnt = 3 → 窗口 [1, 3] 满足条件。
• 当前 cnt = 3 >= 2，则有 n - right + 1 = 7 - 4 + 1 = 4 个符合条件的子数组，ans = 5 + 4 = 9。
• 左指针右移，left = 2，cnt 减少 1。

第三轮外循环 (left = 2)：

• 内循环继续拓展右指针，直到 cnt >= 2：
  • right = 4: a[right] = 6 >= 4, cnt = 3 → 窗口 [2, 4] 满足条件。
• 当前 cnt = 3 >= 2，则有 n - right + 1 = 7 - 5 + 1 = 3 个符合条件的子数组，ans = 9 + 3 = 12。
• 左指针右移，left = 3，cnt 减少 1。

第四轮外循环 (left = 3)：

• 内循环继续拓展右指针，直到 cnt >= 2：
  • right = 5: a[right] = 5 >= 4, cnt = 3 → 窗口 [3, 5] 满足条件。
• 当前 cnt = 3 >= 2，则有 n - right + 1 = 7 - 6 + 1 = 2 个符合条件的子数组，ans = 12 + 2 = 14。
• 左指针右移，left = 4，cnt 减少 1。

第五轮外循环 (left = 4)：

• 内循环继续拓展右指针，直到 cnt >= 2：
  • right = 6: a[right] = 1 < 4, cnt = 2 → 窗口 [4, 6] 满足条件。
• 当前 cnt = 2 >= 2，则有 n - right + 1 = 7 - 7 + 1 = 1 个符合条件的子数组，ans = 14 + 1 = 15。
• 左指针右移，left = 5，cnt 减少 1。

第六轮外循环 (left = 5)：

• 右指针不再需要移动，cnt 少于 k，继续右移左指针，直到遍历结束。

③最终输出

18

【运行结果】