首页 > 试题广场 >

【模板】双指针

[编程题]【模板】双指针
  • 热度指数：330865 时间限制：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
zuve头像 zuve
import sys

n = int(input())
arr = list(map(int,input().split()))
l = 0
res = []
seen = set()
max_len = -1
for r in range(n):
    while arr[r] in seen:
        seen.remove(arr[l])
        l += 1
    seen.add(arr[r])
    cur_len = r-l+1
    if cur_len > max_len:
        max_len = cur_len
        res = [[l+1,r+1]]
    elif cur_len == max_len:
        res.append([l+1,r+1])
print(len(res))
for i in res:
    print(' '.join(map(str,i)))
题目要求位置从1开始，确实还是得注意审题呢
发表于 2026-04-19 15:49:15 回复(0)
牛客397162977号头像 牛客397162977号
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 200005;
int cnt[MAXN]; // 记录窗口内每个数字出现的次数

struct Interval {
    int l, r;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n , len;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    int left = 1;
    int maxLen = 0;
    vector<Interval> results;

    for (int right = 1; right <= n; right++) {
        // 1. 将 a[right] 纳入窗口，计数增加
        cnt[a[right]]++;
        // 2. 如果 a[right] 冲突了（cnt > 1），移动 left 缩小窗口，直到不冲突
        while (cnt[a[right]] > 1)
        {
            cnt[a[left]]--;
            left ++;
        }
        // 3. 计算当前窗口长度 len = right - left + 1
        len = right - left +1;
        // 4. 更新全局最长长度并记录区间
        // 如果 len > maxLen: 清空 results，更新 maxLen，存入新区间
        // 如果 len == maxLen: 直接存入新区间
        if(len > maxLen)
        {
            results.clear();
            results.push_back({left,right});
            maxLen = len;
        }
        else if(len == maxLen)
        {
            results.push_back({left,right});
        }
    }

    // 5. 输出结果
    cout << results.size() << "\n";
    for (auto &res : results) {
        cout << res.l << " " << res.r << "\n";
    }

    return 0;
}
发表于 2026-04-14 20:22:07 回复(0)
Python3
努力学习中_lxj头像 努力学习中_lxj

def two_point() -> int:
    """

    """
    n = int(input())
    list_input = list(map(int, input().split()))
    index_list = []
    ### 存放字母出现次数
    str_dict = {}
    max_len = 0
    left = 0
    for right in range(n):
        if list_input[right] not in str_dict:
            str_dict[list_input[right]] = 1
        else:
            str_dict[list_input[right]] += 1
        ### 当出现大于1的时候，记录最大的长度
        if str_dict[list_input[right]] > 1:
            cur_len = right - left
            if cur_len > max_len:
                max_len = cur_len
                index_list = [(left + 1, right)]
            elif cur_len == max_len:
                index_list.append((left + 1, right))
            #### 左指针移动，对应的字母减少1，直到右侧的字母次数等于1
            while str_dict[list_input[right]] > 1:
                str_dict[list_input[left]] -= 1
                left += 1
        if right == n - 1:
            cur_len = right - left + 1
            if cur_len > max_len:
                max_len = cur_len
                index_list = [(left + 1, right+1)]
            elif cur_len == max_len:
                index_list.append((left + 1, right+1))

    print(len(index_list))
    print('\n'.join([f'{str(i)} {str(j)}' for i, j in index_list]))

two_point()
发表于 2026-03-15 20:10:15 回复(0)
C++
爱看剧的花生米躺平又起来了头像 爱看剧的花生米躺平又起来了
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
//提交可以通过，但是运行时间确实比较长，也许有其他方法可以优化
//这题应该没啥问题
int main() {
    int n;
    cin >> n;
    vector<int>vec(n, 0);
    for (int i = 0; i < n; i++) {
        cin >> vec[i];
    }
    int left = 0, right = 0;
    unordered_map<int, bool>hash;
    hash[vec[0]] = true;
    bool rep = false;//是否含有重复数字
    int re = -1;//重复数字
    int maxlen = 0;//不含重复数字的最长区间

    //双指针找最长区间
    while (right < n) {
        //如果有重复，找出重复数字，左指针右移
        if (rep) {
            if (vec[left] == re) {
                rep = false;
            } else hash[vec[left]] = false;
            left++;
        }
        //如果没有重复，右指针右移
        else {
            right++;
            //如果移到的数字重复，记录重复数字，重复状态并更新最长区间长度
            if (hash[vec[right]]) {
                re = vec[right];
                rep = true;
                maxlen = maxlen > right - left ? maxlen : right - left;
            } else {
                //这里更新区间长度可能导致运行时间超时
                hash[vec[right]] = true;
            }
        }
    }
    vector<pair<int, int>>vp;//满足条件的区间
    int count = 0;//满足条件的区间数
    hash.clear();
    hash[vec[0]] = true;
    left = 0, right = 0;
    rep = false;
    re = -1;
    //重复上述过程
    while (right < n) {
        if (rep) {
            if (vec[left] == re) {
                rep = false;
            } else hash[vec[left]] = false;
            left++;
        } else {
            right++;
            if (hash[vec[right]]) {
                re = vec[right];
                rep = true;
                //在可能的最长区间比较是否是最长区间
                if (right - left == maxlen) {
                    vp.emplace_back(left + 1, right);
                    count++;
                }
            } else {
                hash[vec[right]] = true;
            }
        }
    }
    //循环跳出后补充数组末尾所在的区间没有记录的情况
    if (right - left == maxlen) {
        if (vp[vp.size() - 1].first != left + 1 || vp[vp.size() - 1].second != right) {
            vp.emplace_back(left + 1, right);
            count++;
        }
    }
    cout << count << endl;
    for (const auto& it : vp) {
        cout << it.first << ' ' << it.second << endl;
    }
}
// 64 位输出请用 printf("%lld")
发表于 2026-02-23 21:09:51 回复(0)
牛客879509792号头像 牛客879509792号
#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX_VAL 100000 // 根据数组元素范围调整 int main() { int n; scanf("%d", &n); int *arr = (int *)malloc(n * sizeof(int)); for (int i = 0; i < n; i++) { scanf("%d", &arr[i]); } int last_pos[MAX_VAL + 1]; // 记录元素最后出现的位置，初始化为 -1 memset(last_pos, -1, sizeof(last_pos)); int left = 0; int max_len = 0; int res_count = 0; int *starts = (int *)malloc(n * sizeof(int)); // 存储最长区间的起点（1-based） int *ends = (int *)malloc(n * sizeof(int)); // 存储最长区间的终点（1-based） for (int right = 0; right < n; right++) { // 若当前元素已在窗口内，移动左指针到重复位置的下一位 if (last_pos[arr[right]] != -1 && last_pos[arr[right]] >= left) { left = last_pos[arr[right]] + 1; } last_pos[arr[right]] = right; // 更新当前元素的最后位置 int curr_len = right - left + 1; // 找到更长的区间，重置结果 if (curr_len > max_len) { max_len = curr_len; res_count = 0; starts[res_count] = left + 1; ends[res_count] = right + 1; res_count++; } // 找到等长的区间，加入结果 else if (curr_len == max_len) { starts[res_count] = left + 1; ends[res_count] = right + 1; res_count++; } } // 输出结果 printf("%d\n", res_count); for (int i = 0; i < res_count; i++) { printf("%d %d\n", starts[i], ends[i]); } // 释放内存 free(arr); free(starts); free(ends); return 0; } </string.h></stdlib.h></stdio.h>
发表于 2026-01-10 19:48:18 回复(0)
说谎话的小狗头像 说谎话的小狗
别做，这题有问题
发表于 2025-10-13 01:44:33 回复(0)
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)
Python 3
牛客874416519号头像 牛客874416519号 
a = int(input())
b = input().split(' ')
if a != len(b):exit()
# import random
# b = [random.randint(1,999) for _ in range(9999)]
数量 = 0
区间列表 = []
列表 = list()

for 索引,值 in enumerate(b):
    if 值 in 列表:
        列表 = 列表[列表.index(值)+1:] + [值]
    else:
        列表.append(值)

    if len(列表) > 数量:
        数量 = len(列表)
        区间列表 = [(索引-len(列表)+2,索引+1)]
    elif len(列表) == 数量:
        区间列表.append((索引-len(列表)+2,索引+1))
    # print(索引,值,列表,数量,区间列表)

print(len(区间列表))
for x,y in 区间列表:
    print(fr'{x} {y}')

自己电脑测试秒过，提交却显示超时。也许用更好的数学方***有所改善。





发表于 2025-08-27 22:47:55 回复(0)
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)
rqlwc头像 rqlwc 
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>>ans;
const int N=2e5+10;
int a[N],cnt[N];
int main(){
	int n,ma=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int r=1,l=1;r<=n;r++){
		cnt[a[r]]++;
		while(cnt[a[r]]>1)cnt[a[l]]--,l++;
		if(r-l+1>ma)ans.clear(),ma=r-l+1,ans.push_back(make_pair(l,r));
		else if(r-l+1==ma)ans.push_back(make_pair(l,r));
	}printf("%d\n",ans.size());
	for(auto [l,r]:ans)printf("%d %d\n",l,r);
	return 0;
}

发表于 2025-08-25 20:34:10 回复(0)
Java
六路折梅手头像 六路折梅手 
import java.util.*;
import java.io.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        // 注意 hasNext 和 hasNextLine 的区别
        int n = Integer.parseInt(bf.readLine());
        int[] chs = Arrays.stream(bf.readLine().split(" ")).mapToInt(
                        Integer::parseInt).toArray();

        Map<Integer,Integer> map=new HashMap<>();
        List<int[]> results=new ArrayList<>();
        int maxLen=0;
        int l=0;        

        for (int r = 0; r < n; r++) {
            //右侧先滑动
            map.put(chs[r],map.getOrDefault(chs[r],0)+1);

            //右侧元素个数大于1时，左侧收缩
            while(map.get(chs[r])>1){
                //左侧对应键计数更新
                map.put(chs[l],map.get(chs[l])-1);
                if(map.get(chs[l])==0){
                    map.remove(chs[l]);
                }
                l++;//左侧滑动
            }

            int cur=r-l+1;
            if(cur>maxLen){
                maxLen=cur;
                results.clear();
                results.add(new int[]{l+1,r+1});
            }else if(cur==maxLen){
                results.add(new int[]{l+1,r+1});
            }

        }

        System.out.println(results.size());
        results.forEach(item->System.out.println(item[0]+" "+item[1]));

    }
}

发表于 2025-08-25 11:33:58 回复(0)
提交观点

问题信息

双指针
难度：
11条回答 1381浏览

热门推荐

相关试题

【模板】双指针

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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