Ссылка на задачу с LeetCode — 2179. Count Good Triplets in an Array.
📘 Условие задачи
Даны два массива nums1
и nums2
, являющиеся перестановками чисел от 0
до n-1
.
Нужно найти количество хороших троек (x, y, z)
, таких что:
- индексы этих значений возрастают в обоих массивах:
pos1(x)<pos1(y)<pos1(z)
и pos2(x)<pos2(y)<pos2(z)
,
- где
pos1(v)
и pos2(v)
— позиция значения v
в nums1
и nums2
соответственно.
📌 Пример
- Вход:
nums1 = [2,0,1,3], nums2 = [0,1,2,3]
- Выход:
1
- Пояснение:
- Существуют 4 тройки, удовлетворяющие порядку в
nums1
:
(2,0,1)
, (2,0,3)
, (2,1,3)
, (0,1,3)
- Из них только
(0,1,3)
также удовлетворяет порядку в nums2
.
💡 Идея
Рассматриваем каждое число как средний элемент потенциальной хорошей тройки.
Если знать, сколько подходящих чисел было до него и после него, можно посчитать количество троек с этим числом посередине.
Читать дальше →