当前位置: 首页 > news >正文

算法基础学习|双指针算法

双指针算法

代码模板

for (int i = 0, j = 0; i < n; i ++ ){while (j < i && check(i, j)) j ++ ;// 具体问题的逻辑
}
常见问题分类:(1) 对于一个序列,用两个指针维护一段区间(2) 对于两个序列,维护某种次序,比如归并排序中合并两个有序序列的操作

例题一:最长连续不重复子序列

题目

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

输入格式

第一行包含整数 n

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

输出格式

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

数据范围

1\leq n\leq 10^5

输入样例

5
1 2 2 3 5

输出样例

3

代码示例

#include <iostream>
using namespace std;const int N = 100010;int a[N], s[N];int main(){int n;cin >> n;for(int i = 0; i < n; i++) cin >> a[i];//双指针运算int res = 0;for(int i = 0, j = 0; i < n; i++){s[a[i]]++;while(j < i && s[a[i]] > 1) s[a[j++]]--;//先--后++res = max(res, i - j + 1);}cout << res << endl;
}

例题二:数组元素的目标和

题目

给定两个升序排序的有序数组 A 和 B,以及一个目标值 x

数组下标从 0 开始。

请你求出满足 A[i]+B[j] = x 的数对 (i, j)

数据保证有唯一解。

输入格式

第一行包含三个整数 n, m, x,分别表示 A 的长度,B 的长度以及目标值 x

第二行包含 n 个整数,表示数组 A

第三行包含 m 个整数,表示数组 B

输出格式

共一行,包含两个整数 i 和 j

数据范围

数组长度不超过 10^5
同一数组内元素各不相同。
1\leq 数组元素\leq 10^9

输入样例

4 5 6
1 2 4 7
3 4 6 8 9

输出样例

1 1

代码示例

#include <iostream>
using namespace std;const int N = 100010;int a[N], b[N];int main() {int n, m, x;cin >> n >> m >> x;for (int i = 0; i < n; i++) cin >> a[i];for (int i = 0; i < m; i++) cin >> b[i];for (int i = 0, j = m - 1; i < n; i++){while (j >= 0 && a[i] + b[j] > x) j--;//时间复杂度为O(m+n)if (j >= 0 && a[i] + b[j] == x) cout << i << ' ' << j << endl;}}

例题三:判断子序列

题目

给定一个长度为 n 的整数序列 a_1,a_2,...,a_n 以及一个长度为 m 的整数序列 b_1,b_2,...,b_n

请你判断 a 序列是否为 b 序列的子序列。

子序列指序列的一部分项按原有次序排列而得的序列,例如序列 \left \{ a_1,a_3,a_5 \right \} 是序列 \left \{ a_1,a_2,a_3,a_4,a_5 \right \} 的一个子序列。

输入格式

第一行包含两个整数 n,m

第二行包含 n 个整数,表示 a_1,a_2,...,a_n

第三行包含 m 个整数,表示 b_1,b_2,...,b_n

输出格式

如果 a 序列是 b 序列的子序列,输出一行 Yes

否则,输出 No

数据范围

1\leq n\leq m\leq 10^5,
-10^9\leq a_i,b_i\leq 10^9

输入样例

3 5
1 3 5
1 2 3 4 5

输出样例

Yes

代码示例

#include <iostream>
using namespace std;const int N = 100010;int a[N], b[N];int main() {int n, m;cin >> n >> m;for (int i = 0; i < n; i++) cin >> a[i];for (int i = 0; i < m; i++) cin >> b[i];int i = 0, j = 0; while(i < n && j < m){if(a[i] == b[j]) i++;j++;}if(i == n) cout << "Yes" << endl;else cout << "No" << endl;
}

http://www.lryc.cn/news/287086.html

相关文章:

  • 4.远程登录服务
  • 代码随想录算法训练营第二十九天| 491.递增子序列、46.全排列、47.全排列 II
  • 基于若依的ruoyi-nbcio流程管理系统一种简单的动态表单模拟测试实现(五)
  • 多场景建模:阿里多场景多任务元学习方法M2M
  • 仿真机器人-深度学习CV和激光雷达感知(项目2)day03【机器人简介与ROS基础】
  • 【多商户开源-BSD- Fecmall 电商平台】
  • 2023春秋杯冬季赛 --- Crypto wp
  • ImageMagick使用手册
  • 嵌入式培训机构四个月实训课程笔记(完整版)-C++和QT编程第五天-Qt编程技巧若干解答(物联技术666)
  • 【蓝桥杯选拔赛真题59】python小写字母 第十五届青少年组蓝桥杯python 选拔赛比赛真题解析
  • 代码随想录算法训练营Day37|738.单调递增的数字、贪心算法总结
  • 笔记-影响力-对比,互惠,赌徒原理
  • PIL、cv2、numpy,和pytorch(torch)之间的转换
  • Java面试题50道
  • 电脑怎么剪辑视频?这些软件不可错过
  • HBase学习七:Compaction
  • MySQL定期整理磁盘碎片
  • 【centos7安装docker】
  • 四、Flask学习之JavaScript
  • IO 专题
  • MySql索引事务讲解和(经典面试题)
  • 《微信小程序开发从入门到实战》学习九十一
  • 【立创EDA-PCB设计基础】6.布线铺铜实战及细节详解
  • Node.JS CreateWriteStream(大容量写入文件流优化)
  • 安卓开发之自动缩放布局
  • DDD系列 - 第9讲 实体、值对象
  • 5分钟做自己的微信红包封面
  • pytorch中BCELoss 和 binary_cross_entropy_with_logits之间的区别
  • 无刷电机学习-方波电调 程序篇1(AM32)
  • 如何自己制作一个属于自己的小程序?