双指针算法_Java
模板
for (int r = 0, l = 0; r < n; r++ ) {
while (l < r && check(i, j)) // check(i,j)为不满足的条件
j ++ ; // j向右移动
// 具体问题的逻辑
}
常见问题分类
- 对于一个序列,用两个指针维护一段区间
- 2.对于两个序列,维护某种次序,比如归并排序中合并两个有序序列的操作
思路
首先从暴力解法入手, 观察题目特点, 是否有单调性, 如果有, 可以优化算法, 使用双指针
题目799
从暴力法入手, 所以出现的情况为 n(n - 1) / 2, 时间复杂度为 n^2
发现左指针只可以向右移动, 所有情况为 2n, 时间复杂度为 n
代码
import java.util.Scanner;
public class Main {
private static int N = 100010; // 数据规模为 10w
public static void main(String[] args) {
// 对输入数据进行初始化
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] arr = new int[N];
for (int i = 0; i < n; i++) arr[i] = in.nextInt();
int res = 1;
// s定义: 用于记录 arr数组中 [l, r]元素值出现的个数
// s的下标-> a[i]的值, s[i]中的值-> a[i]的值出现的个数
int[] s = new int[N];
// l代表左指针, r代表右指针
for (int r = 0, l = 0; r < n; r++) {
s[arr[r]]++; // 右指针向右移动, 指向的值的个数 +1
// 如果[l, r]一直有重复元素, l指针向左移动
while (l < r && s[arr[r]] > 1) { // 进行检查
s[arr[l]]--; // 左指针指向的数据的个数 -1
l++; // 左指针向右移动
}
res = Math.max(res, r - l + 1); // 更新最长子序列的值
}
System.out.println(res);
}
}
NZEC怎么回事啊
tql