双指针算法

介绍

双指针算法是指使用两个指针分别指向不同的位置，整个算法过程都维护这两指针，两个指针指向的位置有两类。如下图所示

1. 两个指针分别指向两个序列。
2. 两个指针指向同一个序列。

//模板
for(int i=0, j=0; i < n; i++){
    if(j < i && check(i,j)) j++;
    //每道题的具体逻辑。
}

核心思想与例题

将O(n^{2)的算法优化为O(n)或介于O(n}2)与O(n)之间。

• 例题1：AcWing799.最长连续不重复子序列

给定一个长度为n的整数序列，请找出最长的不包含重复数字的连续区间，输出它的长度。

import java.util.*;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
class Reader{
    static BufferedReader buffer;
    static StringTokenizer token;
    static void init(InputStream input){
        buffer = new BufferedReader(new InputStreamReader(input));
        token = new StringTokenizer("");
    }
    static String next()throws IOException{
        while(!token.hasMoreTokens()){
            token = new StringTokenizer(buffer.readLine());
        }
        return token.nextToken();
    }
    static int nextInt() throws IOException{
        return Integer.parseInt(next());
    }
}
public class Main{
    public static int[] a = new int[100010];
    //a数组用于记录输入的数字。
    public static int[] b = new int[100010];
    //b数组用于记录当前两个指针ij之间所有数字的个数
    public static void main(String[] args)throws IOException{
        Reader.init(System.in);
        int n = Reader.nextInt();
        for(int i = 0; i < n; i++) a[i] = Reader.nextInt();
        int res = 0;
        for(int i = 0,j = 0; i < n; i++){
            //每次i++时，都将新的数字记录到b数组
            b[a[i]]++;
            //一旦当前b数组中新加入的数字的值大于1，说明在j到i中有重复的a[i];
            while(b[a[i]] > 1){
                //从j开始向i的方向枚举，知道找到与a[i]相同的数字;
                b[a[j]]--;
                j++;
            }
            res = Math.max(res,i-j+1);
        }
        System.out.print(res);
    }
}

• 例题2：数组元素的目标和

给定两个升序排序的有序数组A和B，以及一个目标值x。数组下标从0开始。请你求出满足A[i] + B[j] = x的数对(i, j)。数据保证有唯一解
本题暴力算法为遍历两个数组，找到答案，但是因为两个数组都是单调递增的，所以我们可以利用单调性排除掉一些不必要的遍历。

import java.util.*;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
class Reader{
    static BufferedReader buffer;
    static StringTokenizer token;
    static void init(InputStream input){
        buffer = new BufferedReader(new InputStreamReader(input));
        token = new StringTokenizer("");
    }
    static String next()throws IOException{
        while(!token.hasMoreTokens()){
            token = new StringTokenizer(buffer.readLine());
        }
        return token.nextToken();
    }
    static int nextInt() throws IOException{
        return Integer.parseInt(next());
    }
}
public class Main{
    private static int[] a = new int[100010];
    private static int[] b = new int[100010];
    public static void main(String[] args)throws IOException{
        Reader.init(System.in);
        int n = Reader.nextInt(), m = Reader.nextInt(), x = Reader.nextInt();
        for(int i = 0; i < n; i++) a[i] = Reader.nextInt();
        for(int i = 0; i < m; i++) b[i] = Reader.nextInt();
        for(int i = 0,j = m - 1; i < n; i++){
            while(a[i]+b[j]>x){
                j--;
            }
            if(a[i] + b[j] == x){
                System.out.print(i+" "+j);
                break;
            }
        }
    }
}