算法基础-双指针算法

最长连续不重复子序列

1. 双指针[j, i]维护的是以a[i]结尾的最长连续不重复子序列
2. [j, i - 1]是前一步得到的最长连续不重复子序列，所以如果[j, i]中有重复元素，一定是a[i]，所以[j, i - 1]中一定有一个数字与a[i]重复，因此右移j直到a[i]不重复（通过次数来判断）为止
3. 数组s记录子序列a[j ~ i]中各元素出现次数

 

i移动到第二个9，次数为2，j减去1并且右移1位到3
i移动到第二个3，次数为2，j减去1并且右移1位到6

每次都是先减去1再右移，保证每个数字不重复

public class Main {public static void main(String[] args) {int[] a = new int[1000001];int[] s = new int[1000001];Scanner in = new Scanner(System.in);int n = in.nextInt();for(int i = 0; i < n; i ++)a[i] = in.nextInt();int res = 0;for(int i = 0, j = 0; i < n; i ++) {s[a[i]] ++;while(s[a[i]] > 1) {s[a[j]] --;j ++;}res = Math.max(res, i - j + 1);}System.out.println(res);}
}

数组元素的目标和

a数组选的值越大，那么b数组选的值越小，x是固定的

public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int m = in.nextInt();int x = in.nextInt();int[] a = new int[n + 10];int[] b = new int[m + 10];for(int i = 0; i < n; i ++)a[i] = in.nextInt();for(int i = 0; i < m; i ++)b[i] = in.nextInt();for(int i = 0, j = m - 1; i < n; i ++) {while(a[i] + b[j] > x && j >= 0)j --;if(a[i] + b[j] == x && j >= 0) {System.out.println(i + " " + j);break;}}}
}

判断子序列

只需要找到一种情况即可
j 完全遍历一遍，找到的话 i 就往后移动一位，如果 i == n 说明全部找到

public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int m = in.nextInt();int[] a = new int[n + 10];int[] b = new int[m + 10];for(int i = 0; i < n; i ++)a[i] = in.nextInt();for(int i = 0; i < m; i ++)b[i] = in.nextInt();int i = 0, j = 0;while(i < n && j < m) {if(a[i] == b[j])i ++;j ++;}if(i == n)System.out.println("Yes");elseSystem.out.println("No");}
}