双指针
先暴力,看单调性在优化,双指针
双指针是根据性质优化
模板
for (int i = 0, j = 0; i < n; i ++ ) { while (j < i && check(i, j)) j ++ ;
} 常见问题分类: (1) 对于一个序列,用两个指针维护一段区间 (2) 对于两个序列,维护某种次序,比如归并排序中合并两个有序序列的操作
|
题目:
AcWing的
- 799 最长连续不重复子序列
- 800 数组元素的目标和
P799
描述:
给定一个长度为n的整数序列,请找出最长的不包含重复数字的连续区间,输出它的长度。
解答
import java.io.*; import java.util.*;
public class Main { private static int N = 100010; 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; int[] s = new int[N]; for(int r=0,l=0;r<n;r++){ s[arr[r]]++; while(l<r&&s[arr[r]]>1){ s[arr[l]]--; l++; } res = Math.max(res,r-l+1); } System.out.println(res); } }
|
关键:
s定义: 用于记录 arr数组中 [l, r]元素值出现的个数
s的下标-> a[i]的值, s[i]中的值-> a[i]的值出现的个数
往右移动,自然将s[arr[r]],找到不重复的s[arr[l]]–;l,条件是s[arr[r]]不能大于1
P800
描述
给定两个升序排序的有序数组A和B,以及一个目标值x。数组下标从0开始。
请你求出满足A[i] + B[j] = x的数对(i, j)。
关键:升序
解答
import java.io.*; import java.util.*;
public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); String[] strs = br.readLine().split(" "); int n = Integer.parseInt(strs[0]); int m = Integer.parseInt(strs[1]); int x = Integer.parseInt(strs[2]); int[] Aarr = new int[n]; int[] Barr = new int[m]; String[] line1 = br.readLine().split(" "); for(int i = 0; i< n; i++) { Aarr[i] = Integer.parseInt(line1[i]); } String[] line2 = br.readLine().split(" "); for(int i = 0; i< m; i++) { Barr[i] = Integer.parseInt(line2[i]); } int i; int j; for(i=0;i<n;i++){ j=m-1; while(j>=0&&Aarr[i]+Barr[j] > x){ j--; } if(j>=0&&Aarr[i]+Barr[j] == x){ bw.write(i+" "+j); bw.flush(); break; } } br.close(); bw.close(); } }
|
总结
双指针算法,先想暴力做法,再根据性质优化(单调性)
Others
人无完人,何况是小白Chen我呢,文章难免会出现一些错误,若是读者们发现错误,可以评论或者联系我,Chen会尽力改正,给大家更优秀的博文。