基础算法-双指针

双指针

双指针

双指针

顾名思义，两个指针，一般分为左指针和右指针。通过发现某些规律，减小时间复杂度。一般可以将O(n^2)的算法优化到O(n)。双指针的应用非常多，包括归并排序中的归并过程，快速排序中的分割过程。

最长连续不重复子序列

题目地址：最长连续不重复子序列

思路：右指针指向子字符串的最后，左指针指向子字符串的开头，维持左指针到右指针之间没有重复的字符。当右指针向右移动的时候，如果出现重复，肯定是当前右指针指向的这个字符，所以此时移动左指针直到重复字符消失。

代码：

import java.io.*;
import java.util.*;

public class Main{
    
    public static void main(String args[]) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n  = Integer.parseInt(br.readLine());
        String[] vals = br.readLine().split(" ");
        int[] array = new int[n];
        for(int i = 0; i < n; i++){
            array[i] = Integer.parseInt(vals[i]);
        }
        int res = 0;
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int r = 0, l = 0; r < n; r++){
            int v = map.getOrDefault(array[r], 0);
            map.put(array[r], v + 1);
            while(map.getOrDefault(array[r], 0) > 1){
                v = map.getOrDefault(array[l], 0);
                map.put(array[l], v - 1);
                l++;
            }
            res = Math.max(res, r - l + 1);
        }
        System.out.println(res);
    }
}

数组元素的目标和

题目地址：数组元素的目标和

思路：两个数组都是递增的，左指针指向第一个数组的第一个数字，右指针指向第二个数组的最后一个数字。当和值大于目标值时，右指针左移，当和值小于目标值时，左指针右移。

代码：

import java.io.*;

public class Main{
    
    public static void main(String[] args) throws Exception{
        var bf = new BufferedReader(new InputStreamReader(System.in));
        String[] str = bf.readLine().split(" ");
        int n = Integer.parseInt(str[0]);
        int m = Integer.parseInt(str[1]);
        int x = Integer.parseInt(str[2]);
        int[] A = new int[n];
        int[] B = new int[m];
        String[] strA = bf.readLine().split(" ");
        String[] strB = bf.readLine().split(" ");
        for(int i = 0; i < n; i++){
            A[i] = Integer.parseInt(strA[i]);
        }
        for(int i = 0; i < m; i++){
            B[i] = Integer.parseInt(strB[i]);
        }
        int l = 0, r = m - 1;
        while(true){
            int v = A[l] + B[r];
            if(v > x){
                r--;
            }else if(v < x){
                l++;
            }else{
                break;
            }
        }
        System.out.println(l + " " + r);
    }
}

判断子序列

题目地址：判断子序列

思路：i指针指向子序列的第一个字符，j指针指向原字符串的第一个字符，j指针向右寻找i指针指向的字符。找到后，i和j都向后移动一位，重复寻找。

import java.io.*;
public class Main{
    
    public static void main(String[] args) throws Exception{
        var br = new BufferedReader(new InputStreamReader(System.in));
        var str = br.readLine().split(" ");
        int n = Integer.parseInt(str[0]);
        int m = Integer.parseInt(str[1]);
        var A = new int[n];
        var B = new int[m];
        String[] temp = br.readLine().split(" ");
        for(int i = 0; i < n; i++){
            A[i] = Integer.parseInt(temp[i]);
        }
        temp = br.readLine().split(" ");
        for(int i = 0; i < m; i++){
            B[i] = Integer.parseInt(temp[i]);
        }
        boolean flag = true;
        for(int i = 0, j = 0; i < n; i++,j++){
            while(j < m && A[i] != B[j]){
                j++;
            }
            if(j >= m || A[i] != B[j]){
                flag = false;
                break;
            }
        }
        System.out.println(flag ? "Yes" : "No");
    }
}