双指针算法
2022/6/15 1:20:12
本文主要是介绍双指针算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
用处就是优化
例如一道题朴素做法就是暴力遍历,如下:
for(int i = 0; i < n; i++)
for(int j = 0; j <= i; j++)
此时时间复杂度是\(O(n^2)\)的。而通过双指针算法,就可以将其优化为O(n)的。
基本思想如下:
for (int i = 0, j = 0; i < n; i ++ ) { while (j < i && check(i, j)) j ++ ; // 具体问题的逻辑 }
check(i,j)的意思就是满足题目中某种具体要求。
例题
给定一个长度为n的整数序列,请找出最长的不包含重复数字的连续子序列,输出它的长度。
输入格式
第一行包含整数n。
第二行包含n个整数(均在0~100000范围内),表示整数序列。
输出格式
共一行,包含一个整数,表示最长的不包含重复数字的连续子序列的长度。
数据范围
1≤n ≤100000
输入样例
5 1 2 2 3 4输出样例
3
代码
// 本题朴素做法O(n^2) // for(int i = 0; i < n; i++) // for(int j = 0; j <= i; j++) // if(check(j,i)) res = max(res,i-j+1); // 优化之后 // for(int i = 0, j = 0; i < n; i++) // { // 只枚举i。i在右,j在左。j的含义是:j离i往左最远能到什么地方 // 发现规律j只能向后不能向前,因为向前就矛盾了 // check检查i,j区间有没有重复元素 // while(j <= i && check(j,i)) j++; // res = max(res,i-j+1); // } #include<iostream> using namespace std; const int N = 100010; int a[N]; // 原数组 int s[N]; // 当前j~i区间内每一个数出现次数,判断是否有重复 //数据很大时可以用哈希表判重 int n; int main() { cin >> n; for(int i = 0; i < n; i++) cin >> a[i]; int res = 0; for(int i = 0, j = 0; i < n; i++) { // 每次加入一个新的数也就是a[i] s[a[i]]++; // j<=i不用写,当k>i时说明区间没有数,满足要求了 // 新加的数有重复了,重复的一定是a[i] while(s[a[i]] > 1) { // 要把j从这个范围拿出去 s[a[j]]--; j++; } // 此时,i,j之间没有重复元素 res = max(res,i-j+1); } cout << res << endl; return 0; }
这篇关于双指针算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01为什么公共事业机构会偏爱 TiDB :TiDB 数据库在某省妇幼健康管理系统的应用
- 2024-04-26敏捷开发:想要快速交付就必须舍弃产品质量?
- 2024-04-26静态代码分析的这些好处,我竟然都不知道?
- 2024-04-26你在测试金字塔的哪一层?(下)
- 2024-04-26快刀斩乱麻,DevOps让代码评审也自动起来
- 2024-04-262024年最好用的10款ER图神器!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署