// Екі бүтін сан массиві үшін ұзындығы N, // барлық K үшін 1-ден N-ге дейін, K ұзындығындағы префикстердегі жалпы сандардың санын есептеңіз. // Массив ішіндегі сандар қайталануы мүмкін, қиылысу қайталануды ескермей есептеледі. // A массивінің ұзындығы K префиксі – A массивінің алғашқы K элементі // A [1, 1] => [1], [1, 1] // B [1, 1] => [1], [1, 1] // R [1, 1] // [1, 2, 5] => [1], [1, 2], [1, 2, 5] // [1, 5, 4] => [1], [1, 5], [1, 5, 4] // [1, 1, 2]

Міндет: әрбір K үшін 1-ден N-ге дейін, екі массивтің ұзындығы K-ге тең жалпы бірегей сандардың санын есептеу.

Шешім идеясы:

• Әр массивтің префиксіндегі бірегей элементтерді сақтау үшін екі жиын пайдалану.
• 0-ден N-1-ге дейін индекстер бойынша өту, элементтерді сәйкес жиындарға қосу.
• Әр қадамда жиындардың қиылысуын есептеу және қиылысудың өлшемін жазу.

Go тілінде мысал:

package main

import (
	"fmt"
)

func commonPrefixCounts(A, B []int) []int {
	N := len(A)
	setA := make(map[int]struct{})
	setB := make(map[int]struct{})
	result := make([]int, N)

	for i := 0; i < N; i++ {
		setA[A[i]] = struct{}{}
		setB[B[i]] = struct{}{}

		count := 0
		for val := range setA {
			if _, exists := setB[val]; exists {
				count++
			}
		}
		result[i] = count
	}
	return result
}

func main() {
	A := []int{1, 2, 5}
	B := []int{1, 5, 4}
	res := commonPrefixCounts(A, B)
	fmt.Println(res) // Шығу: [1 2 2]
}

Мұндай тәсіл O(N*M) уақытында жұмыс істейді, мұнда M — префикстердегі бірегей элементтердің орташа саны. Оны оңтайландыру үшін жиындар жиынтығы мен жиынтықтың жиілігін есептеу құрылымдарын қолдануға болады.