双指针算法
双指针算法是一种通过维护两个指针来合并两个有序序列的算法。其中，一个指针指向其中一个序列，另一个指针指向另外一个序列。在每次迭代中，两个指针分别移动一步，当两个指针都移动完毕时，整个排序过程结束。双指针算法可以优化朴素算法的时间复杂度，从O(n^2)^ 优化为O(n)。优化后的算法利用了两个指针的单调性，使得我们只需要枚举O(n)个状态，而不是朴素算法中的O(n^2)个状态
代码模板：
1
2
3
4
5
6
7
8
9
| for(i=0,j=0;i<n;i++){
while(j<i&&check(i,j) j++)
//(check()为某个特定条件)
//每道题的逻辑
}
|
例题1：
输入一行字母，每个单词之间有空格，把每个单词放在不同的行
输入样例：
输出样例：
代码：
java：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
String s1=sc.nextLine();
int n=s1.length();
for (int i = 0; i < n; i++) {
int j=i;
while (j<n&&s1.charAt(j)!=' ') j++;
for (int k = i; k < j ; k++) {
System.out.print(s1.charAt(k));
}
System.out.println();
i=j;
}
}
}
|
ps！！：next()与nextLine()比较大的区别是用next()不能得到带空格的字符串,而nextLine()可以。
例题二：
给定一个长度为 n 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。
输入格式
第一行包含整数 n。
第二行包含 n 个整数（均在 0∼10^5 范围内），表示整数序列。
输出格式
共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。
数据范围
1≤n≤10^5
输入样例：
5
1 2 2 3 5
输出样例：
3
代码：
java：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| package org.example;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
final static int N=(int) (1e5+10);
static int[]arr=new int[N];
static int[]s=new int[N];
// 用于记录数组中数字出现的次数
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader= new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(bufferedReader.readLine());
String[] input = bufferedReader.readLine().split(" ");
for (int i = 0; i < n; i++) {
arr[i]=Integer.parseInt(input[i]);
}
int ans=0;
// 区间顺序从j到i
for (int i = 0, j=0; i < n; i++) {
s[arr[i]]++;
while (s[arr[i]]>1&&i>=j) {
s[arr[j]]--;
j++;
}
ans=Math.max(ans, i-j+1);
}
System.out.println(ans);
bufferedReader.close();
}
}
|
