基础算法篇——双指针算法
基础算法篇——双指针算法
本次我们介绍基础算法中的双指针算法，我们会从下面几个角度来介绍：
- 双指针简介
- 双指针基本使用
- 最长连续不重复字符列
- 数组元素的目标和
- 判断子序列
双指针简介
首先我们先来简单介绍一下双指针：
- 双指针算法就是采用两个变量作为指针放在数组的某个部位来实现复杂度简化
我们来介绍一下双指针的使用场景：
- 双指针通常用于简化双for循环的场景，将复杂度为O(N^2)变为O(N)
- 双指针可以用于单个序列中，例如我们之前的快速排序所使用的双指针算法
- 双指针可以用于多个序列中，例如我们之前的归并排序所使用的双指针算法
我们的双指针算法通常是由双for的暴力求解优化得来的：
// 双for循环O(n^2)
for(int i=0;i双指针基本使用
我们首先通过一道基本题来了解双指针：
- 我们给出一个String类型的值，里面装有一些单词，单词由空格隔开，我们需要将他们单独打出来
思路解释：
/*
我们采用双指针算法
i指针指向单词的第一个字母，j指向单词后面的空格，我们只需要输出i和j-1之前的字母并隔开即可
*/
算法实现：
public class BaseAlgorithm {
public static void main(String[] args) {
// 由于是演示，我们这里直接给出数组
String str = new String("cat dog mouse");
// 开始循环(第一层设置i的位置)
for (int i=0;i < str.length();i++) {
// 我们设置j和i同步，让j从单词的第一个字母开始遍历
int j = i;
// 第二层设置j的位置
while (j < str.length() && str.charAt(j) != ' '){
j++;
}
// 输出
for (int k = i; k < j; k++) {
System.out.print(str.charAt(k));
}
System.out.println();
// 重新设置i的位置在j后面（空格后面就是下一个单词的第一个值）
i = j;
}
}
}
最长连续不重复子序列
首先我们介绍题目：
- 给定一个长度为n的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。
思路解释：
// 我们首先假定暴力求解的思路：
for(int i=0;i算法实现：
import java.util.Scanner;
public class UniqueArr {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 输入数组
int n = scanner.nextInt();
int[] arr = new int[n];
for (int i = 0;i < n;i++){
arr[i] = scanner.nextInt();
}
// 存储子序列各数字个数的数组
int[] s = new int[10];
// 返回结果
int res = 0;
// 开始算法
for (int i=0,j=0;i 1){
// j移走相当于移除子序列
s[arr[j]]--;
// 移动j保证其不出现重复数
j++;
}
if (res < i-j+1){
res = i-j+1;
}
}
// 输出
System.out.println(res);
}
}
数组元素的目标和
我们首先来简单介绍题目：
- 给定两个升序排序的有序数组A和B,以及一个目标值x。
- 数组下标从0开始。
- 请你求出满足 A[i]+B[j]=x的数对 (i,j)。
- 数据保证有唯一解。
思路解释：
// 我们首先给出暴力求解
for(int i=0;i算法实现：
import java.util.Scanner;
public class SumX {
public static void main(String[] args) {
// 输入数组长度n，m，以及目标值x
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int x = scanner.nextInt();
// 输入a，b数组
int[] a = new int[n];
int[] b = new int[m];
for (int i = 0; i < n; i++) {
a[i] = scanner.nextInt();
}
for (int i = 0; i < m; i++) {
b[i] = scanner.nextInt();
}
// 开始指针算法
for (int i = 0,j = m - 1; i < n;i++) {
// 判断大于x，就j--使整体变小
while (a[i]+b[j] > x) j--;
// 判断是否等于
if (a[i] + b[j] == x){
System.out.println(i + " " + j);
break;
}
// 没有得到结果，重新循环，i++
}
return;
}
}
判断子序列
我们给出题目：
- 给定一个长度为n的整数序列 a1,a2,…,an以及一个长度为m的整数序列 b1,b2,…,bm
- 请你判断a序列是否为b序列的子序列。
- 子序列指序列的一部分项按原有次序排列而得的序列
思路解释：
// 我们首先给出暴力求解
for(int i=0;i算法实现：
import java.util.Scanner;
public class Son {
public static void main(String[] args) {
// 输入n，m，并赋值
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[] arr = new int[n];
int[] brr = new int[m];
for (int i = 0; i < n; i++) {
arr[i] = scanner.nextInt();
}
for (int i = 0; i < m; i++) {
brr[i] = scanner.nextInt();
}
// 开始算法
int i=0,j=0;
// 首先我们要给出整体判断条件，当两个数组有一个到头就说明遍历已经结束，否则他们会出现数组下标异常
while (i结束语
好的，关于基础算法篇的双指针算法就介绍到这里，希望能为你带来帮助~