Минимальное окно для заданных чисел в массиве

Question

видел этот вопрос недавно:

Учитывая 2 массива, 2-й массив, содержащий некоторые элементы 1-го массива, возвращает минимальное окно в 1-м массиве, которое содержит все элементы 2-го массива.

Например: Дано A = {1,3,5,2,3,1} и B = {1,3,2}

Вывод: 3, 5 (где 3 и 5 - индексы в массиве A)

Даже если диапазон от 1 до 4 также содержит элементы A, возвращается диапазон от 3 до 5, поскольку он содержит, поскольку его длина меньше, чем предыдущий диапазон ((5 - 3) <(4 - 1) )) </strong>

Я разработал решение, но я не уверен, что оно работает правильно, а также неэффективно.

Дайте эффективное решение проблемы. Заранее спасибо

Answer 1

Простое решение итерации по списку.

1. Имеет левый и правый указатель, изначально оба на нуле
2. Перемещайте правый указатель вперед до [L..R]содержит все элементы (или завершается, если право достигает конца).
3. Перемещайте левый указатель вперед, пока [L..R] не будет содержать все элементы.Посмотрите, короче ли [L-1..R], чем текущий лучший.

Это, очевидно, линейное время.Вам просто нужно будет отследить, сколько каждого элемента B находится в подмассиве, чтобы проверить, является ли подмассив потенциальным решением.

Псевдокод этого алгоритма.

size = bestL = A.length;
needed = B.length-1;
found = 0; left=0; right=0;
counts = {}; //counts is a map of (number, count)
for(i in B) counts.put(i, 0);

//Increase right bound
while(right < size) {
    if(!counts.contains(right)) continue;
    amt = count.get(right);
    count.set(right, amt+1);
    if(amt == 0) found++;
    if(found == needed) {
        while(found == needed) {
            //Increase left bound
            if(counts.contains(left)) {
                amt = count.get(left);
                count.set(left, amt-1);
                if(amt == 1) found--;
            }
            left++;
        }
        if(right - left + 2 >= bestL) continue;
        bestL = right - left + 2;
        bestRange = [left-1, right] //inclusive
    }
}