avatar

双指针算法

双指针

先暴力,看单调性在优化,双指针

双指针是根据性质优化

模板

for (int i = 0, j = 0; i < n; i ++ )
{
while (j < i && check(i, j)) j ++ ;

// 具体问题的逻辑
}
常见问题分类:
(1) 对于一个序列,用两个指针维护一段区间
(2) 对于两个序列,维护某种次序,比如归并排序中合并两个有序序列的操作

题目:

AcWing的

  • 799 最长连续不重复子序列
  • 800 数组元素的目标和

P799

描述:

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

解答
import java.io.*;
import java.util.*;

public class Main {
private static int N = 100010; // 数据规模为 10w

public static void main(String[] args){
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] arr = new int[N];
for (int i = 0; i < n; i++) arr[i] = in.nextInt();
int res = 1;
// s定义: 用于记录 arr数组中 [l, r]元素值出现的个数
// s的下标-> a[i]的值, s[i]中的值-> a[i]的值出现的个数
int[] s = new int[N];

for(int r=0,l=0;r<n;r++){
s[arr[r]]++;

while(l<r&&s[arr[r]]>1){
s[arr[l]]--;
l++;
}
res = Math.max(res,r-l+1);
}
System.out.println(res);

}

}

关键:

s定义: 用于记录 arr数组中 [l, r]元素值出现的个数
s的下标-> a[i]的值, s[i]中的值-> a[i]的值出现的个数

往右移动,自然将s[arr[r]],找到不重复的s[arr[l]]–;l,条件是s[arr[r]]不能大于1

P800

描述

给定两个升序排序的有序数组A和B,以及一个目标值x。数组下标从0开始。
请你求出满足A[i] + B[j] = x的数对(i, j)。

关键:升序

解答
import java.io.*;
import java.util.*;

public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

String[] strs = br.readLine().split(" ");
int n = Integer.parseInt(strs[0]); //a[n]
int m = Integer.parseInt(strs[1]); //b[m]
int x = Integer.parseInt(strs[2]);

//输入数组
int[] Aarr = new int[n];
int[] Barr = new int[m];
String[] line1 = br.readLine().split(" ");
for(int i = 0; i< n; i++)
{
Aarr[i] = Integer.parseInt(line1[i]);
}
String[] line2 = br.readLine().split(" ");
for(int i = 0; i< m; i++)
{
Barr[i] = Integer.parseInt(line2[i]);
}

int i;
int j;

//双指针算法
for(i=0;i<n;i++){
j=m-1;
while(j>=0&&Aarr[i]+Barr[j] > x){
j--;
}

if(j>=0&&Aarr[i]+Barr[j] == x){
bw.write(i+" "+j);
bw.flush();
break;
}

}

br.close();
bw.close();


}
}

总结

双指针算法,先想暴力做法,再根据性质优化(单调性)

Others

人无完人,何况是小白Chen我呢,文章难免会出现一些错误,若是读者们发现错误,可以评论或者联系我,Chen会尽力改正,给大家更优秀的博文。

文章作者: Chen
文章链接: https://vccyb.gitee.io/myblog/2020/03/22/Algorithm/articleM-7/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 东川
打赏
  • 微信
    微信
  • 支付寶
    支付寶

评论