双指针算法
优化，降低时间复杂度
- 单区间双指针算法
- 双区间双指针算法
单区间双指针算法
例题：
给定一个长度为 n 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。
输入格式
第一行包含整数 n。
第二行包含 n 个整数（均在 0∼10^5 范围内），表示整数序列。
输出格式
共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。
数据范围
1≤n≤10^5
输入样例：
5 1 2 2 3 5输出样例：
3
import java.util.Scanner;
public class Main {
static int N = (int)1e5 + 10;
static int n;
static int q[] = new int[N];
static int s[] = new int[N];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
for (int i = 0; i < n; i++) {
q[i] = sc.nextInt();
}
int res = 0;
for (int i = 0,j = 0; i < n; i++) {
s[q[i]] ++;
while (s[q[i]] > 1){
s[q[j ++]] --;
}
res = Math.max(res,i - j + 1);
}
System.out.println(res);
sc.close();
}
}优化：O(n^2) — > O(n)
双区间双指针算法
例题：
给定一个长度为 n 的整数序列 a1,a2,…,an 以及一个长度为 mm 的整数序列 b1,b2,…,bm
请你判断 a 序列是否为 b 序列的子序列。
子序列指序列的一部分项按原有次序排列而得的序列，例如序列 {a1,a3,a5} 是序列 {a1,a2,a3,a4,a5} 的一个子序列。
输入格式
第一行包含两个整数 n,m
第二行包含 n 个整数，表示 a1,a2,…,an
第三行包含 m 个整数，表示 b1,b2,…,bm
输出格式
如果 a 序列是 b 序列的子序列，输出一行
Yes。否则，输出
No。数据范围
1≤n≤m≤10^5
−10^9≤ai,bi≤10^9输入样例：
3 5 1 3 5 1 2 3 4 5输出样例：
Yes
import java.util.Scanner;
public class Main {
static int N = (int)1e5 + 10;
static int n,m;
static int a[] = new int[N];
static int b[] = new int[N];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
for (int i = 0; i < m; i++) {
b[i] = sc.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");
else System.out.println("No");
sc.close();
}
}区间合并
例题：
给定 n 个区间 [li,ri]，要求合并所有有交集的区间。
注意如果在端点处相交，也算有交集。
输出合并完成后的区间个数。
例如：[1,3] 和 [2,6] 可以合并为一个区间 [1,6]。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含两个整数 l 和 r。
输出格式
共一行，包含一个整数，表示合并区间完成后的区间个数。
数据范围
1≤n≤100000
−10^9≤li≤ri≤10^9输入样例：
5 1 2 2 4 5 6 7 8 7 9输出样例：
3
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
List<PII> list = new ArrayList<>();
List<PII> res = new ArrayList<>();
for(int i = 0; i < n; i++){
int f = sc.nextInt();
int s = sc.nextInt();
PII pii = new PII(f, s);
list.add(pii);
}
Collections.sort(list,(o1, o2)->{ //先根据左端点排序
if(o1.first != o2.first){
return o1.first - o2.first;
}else{
return o1.second - o2.second ;
}
});
res = merge(list);
System.out.println(res.size());
}
private static ArrayList<PII> merge(List<PII> list){
ArrayList<PII> res = new ArrayList<PII>();
int std = Integer.MIN_VALUE;
int ed = Integer.MIN_VALUE;
for(PII s : list){
if(std == Integer.MIN_VALUE ){ //说明std和ed 还没更新过，初始化一下
std = s.first;
ed = s.second;
}else{
if(ed < s.first){ //说明维护的区间和下一个区间没有交集 ，维护区间就可以先保存了，然后更新到下一个区间
PII ss = new PII(std,ed);
res.add(ss);
std = s.first;
ed = s.second;
}else{//维护的区间和下一个区间有交集，那就看哪个的右端点更大一些
ed = Math.max(ed,s.second);
}
}
}
if(std != Integer.MIN_VALUE ){ //区间有被更新过,如果不加这个代码的话，最后一个区间只是被更新了，并没有被保存
PII ss = new PII(std,ed);
res.add(ss);
}
return res;
}
static class PII{
int first;
int second;
public PII(int f, int s){
this.first = f;
this.second = s;
}
}
}离散化
java：存入id后，结构体排序，rank[num[i].id] = i;直接离散化处理。
C++：unique和lower_bound函数
例题：
假定有一个无限长的数轴，数轴上每个坐标上的数都是 0。
现在，我们首先进行 n 次操作，每次操作将某一位置 x 上的数加 c。
接下来，进行 m 次询问，每个询问包含两个整数 l 和 r，你需要求出在区间 [l,r][l,r] 之间的所有数的和。
输入格式
第一行包含两个整数 n 和 m。
接下来 n 行，每行包含两个整数 x 和 c。
再接下来 m 行，每行包含两个整数 l 和 r。
输出格式
共 m 行，每行输出一个询问中所求的区间内数字和。
数据范围
−10^9≤x≤10^9
1≤n,m≤10^5
−10^9≤l≤r≤10^9
−10000≤c≤10000输入样例：
3 3 1 2 3 6 7 5 1 3 4 6 7 8输出样例：
8 0 5
//离散化
import java.io.*;
import java.lang.Integer;
import java.util.*;
public class Main {
static int N = 300010;
static int[] sum = new int[N];//离散数组，存储前缀和
static TreeMap<Integer, Integer> map = new TreeMap<>();//存储坐标和长度
static ArrayList<Node> query = new ArrayList<>();//用于查询 相当于c++的vector<pair<int,int>>
static int binserySearch(Integer[] index, int x){//二分查找
int l = 0, r = index.length - 1;
while(l < r){
int mid = l + r >> 1;
if(index[mid] < x) l = mid + 1;
else r = mid;
}
return l;
}
public static void main(String[] args)throws Exception{
BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
String[] params = buf.readLine().split(" ");
int n = Integer.valueOf(params[0]);
int m = Integer.valueOf(params[1]);
for(int i = 0; i < n; ++i){
String[] xc = buf.readLine().split(" ");
int x = Integer.valueOf(xc[0]);//构造排序键值
int c = Integer.valueOf(xc[1]);
map.put(x, map.getOrDefault(x, 0) + c);
}
for(int i = 0; i < m; ++i){
String[] lr = buf.readLine().split(" ");
int l = Integer.valueOf(lr[0]);
int r = Integer.valueOf(lr[1]);
map.put(l, map.getOrDefault(l, 0));
map.put(r, map.getOrDefault(r, 0));
query.add(new Node(l, r));//区间读入集合
}
int k = 1;
for(int num : map.values()){//构造前缀和数组
sum[k] = sum[k - 1] + num;
k++;
}
Object[] obj = map.keySet().toArray();
Integer[] index = Arrays.copyOfRange(obj, 0, obj.length, Integer[].class);
for(Node node : query){
int x1 = binserySearch(index, node.first);//查找离散化坐标
int x2 = binserySearch(index, node.second);
int res = sum[x2 + 1] - sum[x1];//计算差值
System.out.printf("%d\n", res);
}
}
}
class Node{//键值对相当于c++的pair<int, int>
public int first;
public int second;
public Node(int first, int second){
this.first = first;
this.second = second;
}
}