基礎演演算法篇——雙指標演演算法

本次我們介紹基礎演演算法中的雙指標演演算法，我們會從下面幾個角度來介紹：

• 雙指標簡介
• 雙指標基本使用
• 最長連續不重複字元列
• 陣列元素的目標和
• 判斷子序列

雙指標簡介

首先我們先來簡單介紹一下雙指標：

• 雙指標演演算法就是採用兩個變數作為指標放在陣列的某個部位來實現複雜度簡化

我們來介紹一下雙指標的使用場景：

• 雙指標通常用於簡化雙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;
    }
}

結束語

好的，關於基礎演演算法篇的雙指標演演算法就介紹到這裡，希望能為你帶來幫助~