基础算法篇——双指针算法

时间：2022-11-07 17:09:09

本次我们介绍基础算法中的双指针算法，我们会从下面几个角度来介绍：

  • 双指针简介
  • 双指针基本使用
  • 最长连续不重复字符列
  • 数组元素的目标和
  • 判断子序列

双指针简介

首先我们先来简单介绍一下双指针：

  • 双指针算法就是采用两个变量作为指针放在数组的某个部位来实现复杂度简化

我们来介绍一下双指针的使用场景：

  • 双指针通常用于简化双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;
    }
}

结束语

好的，关于基础算法篇的双指针算法就介绍到这里，希望能为你带来帮助~

相关文章