#Day53 из #100days_of_coding

Вчера был мой 53-й день кодирования. Я решил один вопрос.

Проблема: Подмножество массива другого массива

Даны два массива: a1[0..n-1] размера n и a2[0..m-1] размера м. Задача состоит в том, чтобы проверить, является ли a2[] подмножеством a1[] или нет. Оба массива могут быть отсортированы или не отсортированы.

Пример 1:

Input:
a1[] = {11, 1, 13, 21, 3, 7}
a2[] = {11, 3, 7, 1}
Output:
Yes
Explanation:
a2[] is a subset of a1[]

Пример 2:

Input:
a1[] = {1, 2, 3, 4, 5, 6}
a2[] = {1, 2, 4}
Output:
Yes
Explanation:
a2[] is a subset of a1[]

Пример 3:

Input:
a1[] = {10, 5, 2, 23, 19}
a2[] = {19, 5, 3}
Output:
No
Explanation:
a2[] is not a subset of a1[]

Ваша задача.
Вам не нужно ничего читать или печатать. Ваша задача — завершить функцию isSubset(), которая принимает массив a1[], a2[], его размер n и m в качестве входных данных и вернуть «Да», если arr2 является подмножеством arr1, иначе вернуть «Нет», если arr2 не является подмножеством arr1.

Ожидаемая временная сложность: O(n)
Ожидаемое вспомогательное пространство: O(n)

Решение (в java). Первым шагом будет сортировка двух массивов.

Установите два указателя i и j или a1[] и a2[] соответственно.
Если a1[i] ‹ a2[j], мы увеличим j на 1.
Если a1[i] = a2[j] , мы увеличим j и i на 1.
Если a1[i] › a2[j], мы завершим работу, так как a2[] не является подмножеством a1[].

class Compute {
    public String isSubset( long a1[], long a2[], long n, long m) {
        
        Arrays.sort(a1);
        Arrays.sort(a2);
        int i=0, j=0;
        while( i<n && j<m){
            if( a1[i]< a2[j])
            i++;
            else if( a1[i]==a2[j]){
            i++;
            j++;
        }
        else if(a1[i]>a2[j])
        return "No";
        
        }
        if( j<m)
        return "No";
        else
        return "Yes";
    }
}