双指针模板
for(int i=0,j=0,i<n;i++){
while(j<i&&check(i,j)) j++;
}
AcWing 799. 最长连续不重复子序列 原题链接
给定一个长度为n的整数序列,请找出最长的不包含重复的数的连续区间,输出它的长度。
输入格式
第一行包含整数n。
第二行包含n个整数(均在0~100000范围内),表示整数序列。
输出格式
共一行,包含一个整数,表示最长的不包含重复的数的连续区间的长度。
数据范围
1≤n≤1000001≤n≤100000
输入样例:
5
1 2 2 3 5
输出样例:
3
public static void main(String[] args) {
int n = in.nextInt();
int[] arr = new int[n];
in.nextIntegerArray(arr);
int res = 0;
Set<Integer> set = new HashSet<>();
int l = 0;
int r = 0;
while (r < n) {
if (!set.contains(arr[r])) {
set.add(arr[r]);
res = Math.max(r - l + 1, res);
}else {
while (set.contains(arr[r])) {
set.remove(arr[l]);
l++;
}
set.add(arr[r]);
}
r++;
}
out.println(res);
out.flush();
out.close();
}
AcWing 800. 数组元素的目标和 原题链接
给定两个升序排序的有序数组A和B,以及一个目标值x。数组下标从0开始。 请你求出满足A[i] + B[j] = x的数对(i, j)。
数据保证有唯一解。
输入格式
第一行包含三个整数n,m,x,分别表示A的长度,B的长度以及目标值x。
第二行包含n个整数,表示数组A。
第三行包含m个整数,表示数组B。
输出格式
共一行,包含两个整数 i 和 j。
数据范围
数组长度不超过100000。 同一数组内元素各不相同。 1≤数组元素≤1091≤数组元素≤109
输入样例:
4 5 6
1 2 4 7
3 4 6 8 9
输出样例:
1 1
public static void main(String[] args) {
int n = in.nextInt();
int m = in.nextInt();
int tar = in.nextInt();
int[] arr = new int[n];
int[] arr2 = new int[m];
in.nextIntegerArray(arr);
in.nextIntegerArray(arr2);
int l = 0;
int r = m - 1;
while (l < n && r >= 0) {
int sum = arr[l] + arr2[r];
if (sum < tar) {
l++;
}else if (sum > tar){
r--;
}else {
break;
}
}
myOut.printArrayJoinSpace(new int[]{l, r});
out.flush();
out.close();
}
AcWing 2816. 判断子序列 原题链接
给定一个长度为 nn 的整数序列 a1,a2,…,ana1,a2,…,an 以及一个长度为 mm 的整数序列 b1,b2,…,bmb1,b2,…,bm。
请你判断 aa 序列是否为 bb 序列的子序列。
子序列指序列的一部分项按原有次序排列而得的序列,例如序列 {a1,a3,a5}{a1,a3,a5} 是序列 {a1,a2,a3,a4,a5}{a1,a2,a3,a4,a5} 的一个子序列。
输入格式
第一行包含两个整数 n,mn,m。
第二行包含 nn 个整数,表示 a1,a2,…,ana1,a2,…,an。
第三行包含 mm 个整数,表示 b1,b2,…,bmb1,b2,…,bm。
输出格式
如果 aa 序列是 bb 序列的子序列,输出一行 Yes
。
否则,输出 No
。
数据范围
1≤n≤m≤1051≤n≤m≤105, −109≤ai,bi≤109−109≤ai,bi≤109
输入样例:
3 5
1 3 5
1 2 3 4 5
输出样例:
Yes
public static void main(String[] args) {
int n = in.nextInt();
int m = in.nextInt();
int[] arr = new int[n];
int[] arr2 = new int[m];
in.nextIntegerArray(arr);
in.nextIntegerArray(arr2);
int idx1 = 0;
int idx2 = 0;
while (idx1 < n && idx2 < m) {
if (arr[idx1] == arr2[idx2]) {
idx1++;
}
idx2++;
}
if (idx1 == n) {
out.println("Yes");
}else {
out.println("No");
}
out.flush();
out.close();
}