Даны два слайса a и b одинаковой длины n. Для каждого k от 1 до n
посчитайте, сколько различных чисел встречается и в префиксе a[:k], и в
префиксе b[:k]. Числа в слайсах могут повторяться; пересечение считается без
учёта кратности. (Обобщение LeetCode 2657 Find the Prefix Common Array — там
массивы являются перестановками.)
// PrefixCommon возвращает res длины n, где res[k-1] — число различных
// значений, входящих и в a[:k], и в b[:k].
func PrefixCommon(a, b []int) []int
Пример
a = [2, 2, 6, 8], b = [6, 2, 8, 2] → [0, 1, 2, 3]
k=1: {2} ∩ {6} = ∅ → 0
k=2: {2} ∩ {6, 2} = {2} → 1
k=3: {2, 6} ∩ {6, 2, 8} = {2, 6} → 2
k=4: {2, 6, 8} ∩ {6, 2, 8} = {2, 6, 8} → 3
Ограничения
0 ≤ n ≤ 10⁶, len(a) == len(b), значения — любые int.- Входные слайсы не изменять.
- Ожидается O(n) в среднем. Пересчитывать пересечение для каждого k заново —
O(n²).
Разбор и эталонное решение — после своей попытки: на собеседовании подсказок не будет.
Сначала попробуй сам — подсказки не дают готовый ответ.