# Double pointer algorithm

### Example 1: longest continuous unrepeated subsequence

Given a sequence of integers with length n, please find the longest continuous interval that does not contain repeated numbers and output its length.

#### Input format

The first line contains the integer n.

The second line contains n integers (all in the range of 0 ∼ 105), representing the integer sequence.

#### Output format

There is one row in total, including an integer, indicating the length of the longest continuous interval that does not contain repeated numbers.

1≤n≤105

```5
1 2 2 3 5
```

#### Output example:

```3
```

```import java.io.BufferedReader;

public class Main {

public static void main(String[] args) throws Exception{
int n = Integer.parseInt(str);
int[] a = new int[n];
for (int i=0;i<n;i++)
a[i] = Integer.parseInt(str[i]);
int[] c = new int;  //b [] record the number of occurrences of each number as a bucket
int res = 0;
for (int i=0,j=0;i<n;i++){  //Double pointer
c[a[i]]++;  //Point to a number and add the number of times of the corresponding number + 1
while (c[a[i]]>1){  //When the number of times > 1, it indicates that there are duplicate elements in the current interval, that is, a[i]
c[a[j]]--;  //Delete the number corresponding to j
j++;
}
res = Math.max(res, i-j+1);     //The maximum value of the length of a continuous interval that does not contain repeated numbers is taken each time
}
System.out.println(res);
}
}

```

### Example 2: target and of array elements

Given two ordered arrays A and B sorted in ascending order, and A target value x.

Array subscripts start at 0.

Please find the number pair (i,j) satisfying A[i]+B[j]=x.

The data is guaranteed to have a unique solution.

#### Input format

The first line contains three integers n, m and x, representing the length of A, the length of B and the target value x.

The second line contains n integers representing array A.

The third line contains m integers representing array B.

#### Output format

A line containing two integers i and j.

#### Data range

The array length does not exceed 105.
The elements in the same array are different.
1 ≤ array element ≤ 109

```4 5 6
1 2 4 7
3 4 6 8 9
```

#### Output example:

```1 1
```

```import java.io.BufferedReader;

public class Main {

public static void main(String[] args) throws Exception {
int n = Integer.parseInt(str);
int m = Integer.parseInt(str);
long x = Long.parseLong(str);
int[] a = new int[n];
int[] b = new int[m];
for (int i = 0; i < n; i++)
a[i] = Integer.parseInt(str[i]);
for (int i = 0; i < m; i++)
b[i] = Integer.parseInt(str[i]);
for (int i = 0, j = m - 1; i < n; i++) {
if (a[i] < x) {
while (j >= 0 && a[i] + b[j] > x) {
j--;
}
if (j >= 0 && a[i] + b[j] == x) {
System.out.println(i + " " + j);
break;
}
}
j = m - 1;
}
}
}
```

### Example 3: judgment subsequence

Given an integer sequence a1,a2,..., an of length n and an integer sequence b1,b2,..., bm of length m.

Please judge whether a sequence is a subsequence of b sequence.

Subsequence refers to the sequence obtained by arranging some items of the sequence in the original order. For example, sequence {a1,a3,a5} is a subsequence of sequence {a1,a2,a3,a4,a5}.

#### Input format

The first line contains two integers n,m.

The second line contains n integers representing a1,a2,..., an.

The third line contains m integers representing b1,b2,..., bm.

#### Output format

If a sequence is a subsequence of b sequence, a line of Yes is output.

Otherwise, output No.

1≤n≤m≤105,
−109≤ai,bi≤109

```3 5
1 3 5
1 2 3 4 5
```

#### Output example:

```Yes
```

```import java.io.BufferedReader;

public class Main {

public static void main(String[] args) throws Exception {
int n = Integer.parseInt(str);
int m = Integer.parseInt(str);
int[] a = new int[n];
int[] b = new int[m];
for (int i = 0; i < n; i++)
a[i] = Integer.parseInt(str[i]);
for (int i = 0; i < m; i++)
b[i] = Integer.parseInt(str[i]);
int i=0, j=0;
while (i<n&&j<m){
if(a[i]==b[j])
i++;
j++;
}
if(i==n)
System.out.println("Yes");
else
System.out.println("No");
}
}

```

Keywords: Algorithm

Added by Candrew on Wed, 27 Oct 2021 07:44:59 +0300