基礎演算法篇——雙指針演算法
基礎演算法篇——雙指針演算法
本次我們介紹基礎演算法中的雙指針演算法，我們會從下面幾個角度來介紹：
- 雙指針簡介
- 雙指針基本使用
- 最長連續不重複字元列
- 數組元素的目標和
- 判斷子序列
雙指針簡介
首先我們先來簡單介紹一下雙指針：
- 雙指針演算法就是採用兩個變數作為指針放在數組的某個部位來實現複雜度簡化
我們來介紹一下雙指針的使用場景：
- 雙指針通常用於簡化雙for循環的場景，將複雜度為O(N^2)變為O(N)
- 雙指針可以用於單個序列中，例如我們之前的快速排序所使用的雙指針演算法
- 雙指針可以用於多個序列中，例如我們之前的歸併排序所使用的雙指針演算法
我們的雙指針演算法通常是由雙for的暴力求解優化得來的：
// 雙for循環O(n^2)
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
// 實現流程
}
}
// 雙指針演算法O(n)
for(int i=0,j=0;i<n;i++){
while(j<i && check(i,j)){
// 實現流程
}
}
雙指針基本使用
我們首先通過一道基本題來了解雙指針：
- 我們給出一個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<arr.length;i++){
for(int j=0;j<arr.length;j++){
// 判斷是否滿足條件，滿足即更換result
}
}
// 首先我們需要保證我們輸入的數是具有單調性的，這樣才可以保證雙指針演算法的實現
/*
我們首先選中指針i作為子序列的右側，一直向右運行
我們然後選中指針j作為子序列的左側，沒有特殊情況下不用移動，負責控制錯誤
我們需要保證j~i之間沒有重複數，因為我們需要讓i一直右移實現動態，所以當出現重複數時我們只能移動j來保證沒有重複數
同時我們採用s[]數組來存儲0~9之間的數的該子序列的出現次數
即i經過時s[i]++,j經過時s[j]--即可
*/
演算法實現：
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<arr.length;i++){
// i指針經過相當於存入子序列
s[arr[i]]++;
// 判斷存在出現重複數
while (s[arr[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<a.length;i++){
for(int j=0;j<b.length;j++){
if(a[i] + b[j] == x){
return i,j;
}
}
}
/*
然後我們可以根據模板進行思考
我們的x是由a和b數組的數組成，且a和b都是順序排列，如果我們將指針i從a的開頭，將指針j從b的結尾來開始運算
當他倆的和相加小於x，i++；當他倆的和大於x，j--；知道最後判定出來~(注意：人家說了必定有唯一解)
*/
演算法實現：
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<a.length;i++){
for(int j=0;j<b.length;b++){
// 判斷a[i]==b[j]，如果是就繼續，如果不是說明不是子序列，直接pass
}
}
/*
我們進行進一步解析
我們的i，j都是從a，b的開頭開始
但是數組都是按照正序排列，所以如果i和j所對應的值相等時，i+1的值只能在j後面，我們可以利用這個特性
*/
演算法實現：
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<n && j<m){
// 判斷是否相同，相同的話i++
if (arr[i] == brr[j]){
i++;
}
// 無論是否相同，j++
j++;
}
// 最後判斷，如果arr全部遍歷了一遍，則說明是子序列
if (i == n){
System.out.println("是子序列");
}else {
System.out.println("不是子序列");
}
return;
}
}
結束語
好的，關於基礎演算法篇的雙指針演算法就介紹到這裡，希望能為你帶來幫助~
