Уровень сложности: средний
Понимание проблемы
Описание проблемы. Дан массив различных целых чисел и значение суммы. Найдите количество троек, сумма которых меньше заданного значения суммы.
Для этой задачи нам нужно найти количество троек, а не троек чисел.
Пример:
Ввод: arr[] = { 3, 4, 7,1,5}
val = 12.
Вывод: 4
Объяснение: Ниже приведены триплеты с суммой меньше 12
(1, 3, 4), (1, 3, 5), (1, 3, 7) и (1, 4, 5)
Возможные решения:
- Brute Force: использование 3 циклов для рассмотрения всех случаев
- Эффективный подход: сортировка по принципу «встречаться посередине».
1. Brute Force: использование 3 циклов для рассмотрения всех троек
Подход Brute Force заключается в рассмотрении всех триплетов путем повторения массива с использованием 3 циклов, каждый цикл для каждого элемента триплета. Будут рассмотрены только те триплеты, общая сумма которых меньше желаемого значения суммы.
код: c++
2. Эффективный подход: сортировка по принципу «встречаться посередине».
Эффективный подход включает в себя сначала сортировку массива, а затем применение метода встречи посередине для эффективного подсчета всех возможных случаев триплетов, не перебирая все триплеты.
Для встречи в средней части мы создаем два указателя, которые учитывают левый индекс и правый индекс соответственно отсортированного массива.
После этого мы запускаем цикл for, и каждый элемент рассматривается, где левый индекс будет указывать индекс рядом с рассматриваемым элементом, а правый индекс будет указывать последний индекс массива.
Затем мы подсчитываем сумму триплета, созданного как:
sum = arr[ind]+arr[left_ind] + arr[right_ind] .
Если сумма меньше желаемого значения, то все элементы, лежащие между левым и правым индексом, будут иметь значение меньше желаемого значения. Следовательно, мы можем увеличить результирующий счет на:
cnt = cnt + (right_ind-left_ind) ;
В противном случае, если сумма больше требуемого значения, мы уменьшаем значение правого индекса на 1, чтобы рассматривать следующий элемент в отсортированном массиве. то есть: right_ind = right_ind -1 ;
Временная сложность: сортировка требует O(nlogn) времени и встреча в средней части состоит из цикла for и левого и правого указателя, который выполняет итерацию от 0 до n-1 индекса в начальные случаи, которые дают второй части временную сложность: O(n)*O(n) = O(n²).
Следовательно, амортизированная временная сложность этого подхода составляет O(n²) .
