首页 > 试题广场 >

【模板】双指针

[编程题]【模板】双指针
  • 热度指数：328957 时间限制：C/C++ 4秒，其他语言8秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}对于给定的长度为 n 的数组 \{a_1,a_2,\dots,a_n\} ，找出最长的区间，满足区间中元素两两不同。
\hspace{15pt}如果有多个这样的区间，依次输出它们。

输入描述:
\hspace{15pt}第一行输入一个整数 n \left( 1 \leqq n \leqq 2 \times 10^5\right) 代表数组中的元素数量。
\hspace{15pt}第二行输入 n 个整数 a_1,a_2,\dots,a_n \left( 0 \leqq a_i \leqq n \right) 代表初始数组。


输出描述:
\hspace{15pt}第一行输出一个整数 m \left( 1 \leqq m \leqq n \right) 代表满足条件的区间数量。
\hspace{15pt}此后 m 行，每行输出两个整数 l,r \left( 1 \leqq l \leqq r \leqq n \right) 代表满足条件的区间。本题没有 \sf SPJ ，请按照 l 递增的顺序输出。
示例1

输入

6
1 1 4 5 1 4

输出

3
2 4
3 5
4 6
算法知识视频讲解
添加回答
Python3
牛客746148623号头像 牛客746148623号
def get_max_qujian(n, a_list):
    res = []
    max_len = 0
    n = len(a_list)  # 使用实际长度，避免输入的n与实际列表长度不符
    a_map = {}
    left = 0
    for i in range(n):
        num = a_list[i]
        if num in a_map and a_map[num] >= left:
            left = a_map[num] + 1
        a_map[num] = i
        cur_len = i-left
        if cur_len > max_len:
            max_len = cur_len
            res = [(left+1,i+1)]
        elif cur_len == max_len:
            res.append((left+1,i+1))

    # 输出结果
    print(len(res))
    for interval in res:
        print(interval[0], interval[1])

if __name__ == "__main__":
    n = input()
    a_list = input()
    a_list = a_list.split(" ")
    a_list = list(map(int,a_list))
    get_max_qujian(n,a_list)

       


发表于 2025-09-19 00:55:42 回复(1)
Python3
牛客847294653号头像 牛客847294653号
#被0.12%的通过率吓到了
n = int(input())
a = list(map(int, input().split()))

max_len = 0  # 最长区间长度
max_intervals = []  # 存储所有最长区间

left = 0
right = 0
s = set()  # 当前窗口中的元素集合

while right < n:
    # 如果右指针指向的元素不在当前集合中
    if a[right] not in s:
        s.add(a[right])
        right += 1

        # 检查是否找到了更长的区间
        current_len = right - left
        if current_len > max_len:
            max_len = current_len
            max_intervals = [(left + 1, right)]  # 从1开始计数
        elif current_len == max_len:
            max_intervals.append((left + 1, right))  # 添加等长区间
    else:
        # 当遇到重复元素时，移动左指针直到重复元素被移除
        s.remove(a[left])
        left += 1

# 按照左边界递增排序
max_intervals.sort()

# 输出结果
print(len(max_intervals))
for l, r in max_intervals:
    print(l, r)

发表于 2025-08-26 22:27:17 回复(0)
提交观点

问题信息

双指针
难度：
2条回答 671浏览

热门推荐

相关试题

【模板】双指针

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号