Задания № 25, 26 · ЕГЭ

Поиск тройки элементов

Как найти три элемента массива с заданными свойствами

2 мин чтенияСложность: Обновлено 29 сентября 2026

Поиск тройки элементов — это задача нахождения трёх элементов массива, которые вместе удовлетворяют заданному условию: имеют нужную сумму, образуют комбинацию или обладают другими свойствами. Решение строят полным перебором или более быстрым алгоритмом после сортировки.

Поиск тройки элементов — перебор или эффективное нахождение индексов \(i\), \(j\), \(k\) трёх различных элементов массива, для которых выполняется заданное условие. Обычно индексы должны быть различны, а иногда дополнительно требуется \(i < j < k\).

\[\sum_{i=0}^{n-3}\sum_{j=i+1}^{n-2}\sum_{k=j+1}^{n-1} [P(a_i,a_j,a_k)]\]1

В формуле перебираются все тройки индексов, а \(P\) — проверяемое условие. Количество таких троек равно \(\binom{n}{3}=\frac{n(n-1)(n-2)}{6}\), поэтому прямой алгоритм имеет сложность \(O(n^3)\). Для небольших массивов этого достаточно.

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

№

Пример

В массиве \([1, 4, 6, 8, 10]\) ищем три числа с суммой \(18\). Выбираем \(1\), а затем ищем пару с суммой \(17\): \(8+9\) не подходит, но при переборе других вариантов находится \(4+10\). Значит, тройка \(1,4,10\) подходит.

Не перепутайте

Три элемента должны быть различными элементами массива, а не обязательно различными значениями. Например, в массиве \([2,2,5]\) два элемента со значением \(2\) можно выбрать, если они находятся в разных позициях. Нельзя использовать один и тот же индекс дважды.

Проверка

Какова сложность полного перебора всех троек элементов массива длины \(n\)?

Главное за минуту

Главное

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