HJ178. 【模板】双指针
题目描述
给定长度为 n 的数组，找出最长的区间，满足区间内元素两两不同。若有多个这样的区间，依次输出它们。
输入格式
- 第 1 行：n
- 第 2 行：n 个整数
输出格式
- 第 1 行：满足条件的区间数量
- 接下来每行：区间的左右端点 L、R（1 基，L 递增）
示例
示例 1
输入：
6
1 1 4 5 1 4
输出：
3
2 4
3 5
4 6
说明：
区间 [2,4]=[1,4,5]、[3,5]=[4,5,1]、[4,6]=[5,1,4] 长度为 3，均无重复元素，是最长的三个区间。
解题思路
第一步：理解问题本质
找到所有最长的"无重复元素"连续子数组。用双指针维护一个不含重复元素的滑动窗口。
第二步：暴力解法（枚举所有区间）
枚举所有左端点和右端点，检查区间内是否无重复，记录最长的。
问题：区间数为 O(n²)，每个区间检查去重 O(n)，总复杂度 O(n³)，无法接受。
第三步：优化解法（双指针滑动窗口）
维护窗口 [left, right]，保证窗口内元素两两不同：
- 右指针
right不断扩展 - 若新元素
arr[right]在窗口内已出现，则左指针left移到它上一次出现位置的下一个，保证无重复
用 last_pos 哈希表记录每个元素最近一次出现的位置：
last_pos = {}
left = 0
for right in range(n):
v = arr[right]
if v in last_pos and last_pos[v] >= left:
left = last_pos[v] + 1
last_pos[v] = right
cur_len = right - left + 1
# 更新最长长度并记录区间
第四步：最优解法
记录并更新最长长度；长度相同时记录所有区间（转 1 基输出）。每个元素进出窗口一次，整体 O(n)，是最优解法。
完整代码实现
算法可视化 · 逐帧回放这道题的代码68 帧 · 录制输入
import sys
def solve() -> None:
data = sys.stdin.buffer.read().split()
n = int(data[0])
arr = list(map(int, data[1:1 + n]))
last_pos = {} # 元素 -> 最近一次出现的位置
left = 0 # 窗口左端点
best = 0
intervals = []
for right in range(n):
v = arr[right]
# 若 v 在窗口内已出现，则左指针移到其上一次出现位置的下一个
if v in last_pos and last_pos[v] >= left:
left = last_pos[v] + 1
last_pos[v] = right
cur_len = right - left + 1
if cur_len > best:
best = cur_len
intervals = [(left + 1, right + 1)] # 转 1 基
elif cur_len == best:
intervals.append((left + 1, right + 1))
print(len(intervals))
for l, r in intervals:
print(l, r)
if __name__ == "__main__":
solve()
示例推演
以示例 1 为例，n=6，数组 [1, 1, 4, 5, 1, 4]（下标 0~5）。
用 last_pos 记录每个元素最近位置，left 为窗口左端点：
right=0值 1：未出现，last_pos[1]=0，窗口[0,0]长 1。best=1，区间[1,1]right=1值 1：last_pos[1]=0 >= left=0，left=1，last_pos[1]=1，窗口[1,1]长 1right=2值 4：未出现，last_pos[4]=2，窗口[1,2]长 2。best=2，区间[2,3]right=3值 5：未出现，last_pos[5]=3，窗口[1,3]长 3。best=3，区间[2,4]right=4值 1：last_pos[1]=1 >= left=1，left=2，last_pos[1]=4，窗口[2,4]长 3。等于 best，追加区间[3,5]right=5值 4：last_pos[4]=2 >= left=2，left=3，last_pos[4]=5，窗口[3,5]长 3。追加区间[4,6]
最终 best=3，三个最长区间（1 基）：[2,4]、[3,5]、[4,6]。
输出：
3
2 4
3 5
4 6
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 暴力枚举 | O(n³) | O(n) | 区间数与检查均开销大 |
| 双指针 | O(n) | O(n) | 每元素进出窗口各一次 |
n 为数组长度
易错点总结
1. 左指针移动位置错误
当 arr[right] 已在窗口内时，left 要跳到 last_pos[v] + 1，不是简单 left += 1。只有 last_pos[v] >= left（即在当前窗口内）时才需要移动。
2. 忘记更新 last_pos
每次处理完都要 last_pos[v] = right 更新最近位置，否则后续重复判断会出错。
3. 1 基 / 0 基混淆
内部用 0 基下标，输出区间端点时要转成 1 基（+1），否则输出错误。
扩展思考
- 双指针滑动窗口是解决"最长无重复子数组/子串"问题的标准模板，可用于求最短覆盖、连续子数组和等变体。
- 与 HJ176 单调队列都属于"滑动窗口"家族，但应用场景不同：前者求最值，后者求无重复最长区间。