您的位置:首页 > 文旅 > 旅游 > 算法刷题笔记 最长连续不重复子序列(C++实现)

算法刷题笔记 最长连续不重复子序列(C++实现)

2024/12/23 11:40:32 来源:https://blog.csdn.net/hanmo22357/article/details/139353721  浏览:    关键词:算法刷题笔记 最长连续不重复子序列(C++实现)

文章目录

    • 题目描述
    • 解题思路
    • 实现代码

题目描述

  • 给定一个长度为n的整数序列,请找出最长的不包含重复的数的连续区间,输出它的长度。

输入格式

  • 第一行包含整数n
  • 第二行包含n个整数(均在 0∼10^5范围内),表示整数序列。

输出格式

  • 共一行,包含一个整数,表示最长的不包含重复的数的连续区间的长度。

数据范围

  • 1 ≤ n ≤ 10^5

解题思路

这道题实际上就是一道双指针算法题,其解题思路基本上和我之前的一篇博文 力扣刷题笔记3 无重复字符的最长子串 完全类似。那一道题目借鉴了哈希集合,用于以字符为键,查找当前右指针指向的元素是否在集合中。本题实际更简单一些,只需要用整数位键来查找即可。因此,不难联想到我们可以直接使用最简单的数组进行查找,因为数组可以被简单视为键为整数的哈希集合。所以得到的代码如下。

实现代码

#include <cstdio>const int N(1e5 + 10);
int arr[N];
bool record[N];int main(void)
{int n;scanf("%d", &n);int max_length(0);for(int i(0); i < n; ++i){scanf("%d", &arr[i]);}for(int left(0), right(0); left < n; ++left){while(record[arr[right]] == false && right < n){record[arr[right++]] = true;max_length = (right - left > max_length) ? right - left : max_length;}record[arr[left]] = false;}printf("%d", max_length);return 0;
}
  • 注意事项:在编程的过程中,一定不能为了追求代码的简洁而将多个步骤合并,否则检查和调试过程非常麻烦。

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com