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.

Data range

1≤n≤105

Input example:

5
1 2 2 3 5

Output example:

3

answer:

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws Exception{
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String[] str = bufferedReader.readLine().split(" ");
        int n = Integer.parseInt(str[0]);
        int[] a = new int[n];
        str = bufferedReader.readLine().split(" ");
        for (int i=0;i<n;i++)
            a[i] = Integer.parseInt(str[i]);
        int[] c = new int[100001];  //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

Input example:

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

Output example:

1 1

answer:

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String[] str = bufferedReader.readLine().split(" ");
        int n = Integer.parseInt(str[0]);
        int m = Integer.parseInt(str[1]);
        long x = Long.parseLong(str[2]);
        int[] a = new int[n];
        int[] b = new int[m];
        str = bufferedReader.readLine().split(" ");
        for (int i = 0; i < n; i++)
            a[i] = Integer.parseInt(str[i]);
        str = bufferedReader.readLine().split(" ");
        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.

Data range

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

Input example:

3 5
1 3 5
1 2 3 4 5

Output example:

Yes

answer:

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String[] str = bufferedReader.readLine().split(" ");
        int n = Integer.parseInt(str[0]);
        int m = Integer.parseInt(str[1]);
        int[] a = new int[n];
        int[] b = new int[m];
        str = bufferedReader.readLine().split(" ");
        for (int i = 0; i < n; i++)
            a[i] = Integer.parseInt(str[i]);
        str = bufferedReader.readLine().split(" ");
        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");
    }
}