Блог

Есть 2 массива A и B с длинами N и M, которые вы должны удалить по 1 элементу за раз из B и проверить, существует ли перестановка B в A

Пояснение: Пример:

 N = 5
A = [1,2,2,1,1]
M = 3
b = [1,2,1]
Output: [0,2,3]
 

Когда вы удаляете 1-й элемент из B, он становится [2,1]. Вы можете видеть в массиве A, что подмножество длины 2, начинающееся с индекса 0, равно [1,2], и поскольку [1,2] является перестановкой [2,1], у вас есть соответствие, соответствующее этому подмножеству. Аналогично, подмножество, начинающееся с индекса 2, также совпадает. Таким образом, теперь у вас есть 2 совпадения, соответствующие индексам 0 и 2. Теперь массив B восстановлен B = [1,2,1]

Теперь, когда вы удаляете 2-й элемент из B, он становится [1,1]. Для этого вы можете найти 1 совпадение, соответствующее подмассиву, начиная с индекса 3

удаление 3-го элемента бесполезно, так как мы удалили 1 раньше и проверили его

Следовательно, ответ [0,2,3]

Если мы ищем сложность O(n^2), хэшируйте каждое окно в A, где ключом является отсортированный список элементов в окне, а значениями являются индексы, где он виден. Для вашего примера мы бы:

 [1,2,2,1,1]

1,1,1,2,2 -> [0]
1,1,2,2   -> [0, 1]
1,2,2     -> [0, 1]
...
1,2       -> [0, 2]
etc.
 

мы также могли бы использовать мультимножество для ключа, если ожидается много дубликатов, например:

 1:3,2:2 -> [0]
 

Теперь создайте соответствующий ключ для каждого элемента, удаленного в B, по мере прохождения, и проверьте, есть ли ключ в хэш-таблице.

 B: {1: 2, 2: 1}

Traverse:

Key 1:1,2:1 -> indexes [0, 2]
...etc.