双指针算法模板：
for (int i = 0, j = 0; i < n; i ++ ){while (j < i && check(i, j)) j ++ ;// 具体问题的逻辑}
常见问题分类：
(1) 对于一个序列，用两个指针维护一段区间
(2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作
最长连续不重复子序列
https://www.acwing.com/problem/content/801/
final static int N=100010; public static void main(String[] args) throws IOException { int []arr=new int[N]; BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); int n=Integer.parseInt(br.readLine().split(" ")[0]); String []str=br.readLine().split(" "); for (int i = 0; i < n; i++) { arr[i]=Integer.parseInt(str[i]); } int []s=new int[N]; int max=0; for(int i=0,j=0;i<n;i++){ s[arr[i]]++; while (j<i &&s[arr[i]]>1){ s[arr[j]]--; j++; } max=Math.max(max,i-j+1); } System.out.println(max); }
数组元素的目标和
https://www.acwing.com/problem/content/802/
final static int N=100010; public static void main(String[] args) throws IOException { int[] arrN = new int[N]; int[] arrM = new int[N]; BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String s= br.readLine(); int n = Integer.parseInt(s.split(" ")[0]); int m = Integer.parseInt(s.split(" ")[1]); int x = Integer.parseInt(s.split(" ")[2]); String []s1= br.readLine().split(" "); for (int i = 0; i < n; i++) { arrN[i]=Integer.parseInt(s1[i]); } String []s2= br.readLine().split(" "); for (int i = 0; i < m; i++) { arrM[i]=Integer.parseInt(s2[i]); } br.close(); for(int i=0,j=m-1;i<n;i++){ while (j>0 &&arrN[i]+arrM[j]>x){ j--; } if(arrN[i]+arrM[j]==x){ System.out.println(i+" "+j); break; } } }
判断子序列
https://www.acwing.com/problem/content/2818/
final static int N=100010; public static void main(String[] args) throws IOException { int[] a = new int[N]; int[] b = new int[N]; BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String []s= br.readLine().split(" "); int n=Integer.parseInt(s[0]),m=Integer.parseInt(s[1]); String []s1= br.readLine().split(" "); for (int i = 0; i < n; i++) { a[i]=Integer.parseInt(s1[i]); } String []s2= br.readLine().split(" "); for (int i = 0; i < m; i++) { b[i]=Integer.parseInt(s2[i]); } int i = 0, j = 0; while(i < n && j < m){ if(a[i] == b[j]) i ++; j ++; } if(i == n) System.out.println("Yes"); else System.out.println("No"); }
位运算：
二进制中1的个数
https://www.acwing.com/problem/content/803/
按位与：a&b是把a和b都转换成二进制数然后再进行与的运算；
进入正题
二进制中1的个数，
本题是通过找出x的二进制位中最末尾出现的1的位置，用二进制表示出来
假设 x = 9 即 0 1001，-x为x的反码+1
-x = ~x + 1即1 0111 =>1 0110 + 1 =1 0111
x & -x
0 1001
& 1 0111
————————————
0 0001
用x - (x&-x) = 1000,这样我们即得到了一个1，同时将该1的位置从数x中去除
public static void main(String[] args) throws IOException { BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); String []s=br.readLine().split(" "); int n=Integer.parseInt(s[0]); String []s1=br.readLine().split(" "); int x=0; for (int i = 0; i < n; i++) { x=Integer.parseInt(s1[i]); int count=0; while (x!=0){ x-=lowbit(x); count++; } System.out.print(count+" "); } } public static int lowbit(int x){ return x&-x; }
