Постановка задачи

Имея массив arr несортированных чисел и целевую сумму, сосчитайте все триплеты в нем так, чтобы arr+arr+ arr ‹ targetгде i, j и k — три разных индекса. Напишите функцию, которая возвращает количество таких троек.

Пример 1:

Входные данные: , target=3
Выходные данные: 2
Объяснение: Есть две тройки, сумма которых меньше целевой: ,


Пример 2:

Ввод: , target=5
Вывод: 4
Объяснение: Есть четыре триплета, сумма которых меньше целевой:
, , ,


Решение

Эта задача следует шаблону Два указателя (аналогично бинарному поиску) и имеет сходство с задачей Сумма троек к нулю. Разница лишь в том, что в этой задаче нам нужно найти триплеты, сумма которых меньше заданной цели. Чтобы выполнить условие i!=j!=k,в тройке, нужно убедиться, что каждое число не используется более одного раза.

Следуя аналогичному подходу, сначала мы можем отсортировать массив, а затем пройтись по нему, беря по одному числу за раз. Допустим, во время нашей итерации мы находимся под номером X, поэтому нам нужно найти Y и Z так, чтобы X + Y + Z ‹ цель. На данном этапе наша задача сводится к поиску пары, сумма которой меньше, чем $ target — X$ (как из приведенного выше уравнения Y + Z == target — X). Мы можем использовать аналогичный подход, описанный в Проблеме тройной суммы до нуля.

В цикле мы, по сути, находим минимальный и максимальный диапазон низких и высоких значений индекса для Y и Z, где X+Y+Z ‹ target и, таким образом, для подсчета количества троек мы прибавляем к подсчету разницу между высокими и низкими индексами, т.е. count += high — low;

Код JavaScript ниже:-

function Triplet_with_smaller_sum(arr, target) {
// TODO: напишите здесь свой код
let count = 0;
arr.sort((a,b)=›ab);
> for (var index = 0; index ‹ arr.length; index++) {
count += search_pair(arr, target — arr, index);
}
return count;
> };
function search_pair(arr, target, index) {
var low = index + 1,
high = arr.length — 1,
count = 0;
/> while (low ‹ high) {
if (arr + arr ‹ target) {
count += high — low;
console.log(low, high, arr, arr, target );
low++;
} else {
high — ;
}
}
счетчик возврата;
}
документ. write(triplet_with_smaller_sum(, 3)+'
');
document.write(triplet_with_smaller_sum(, 5)+'
');


Временная сложность

Сортировка массива займет O(N * logN). search_pair() займет O(N). Таким образом, в целом triplet_with_smaller_sum() займет O(N * logN + N²), что асимптотически эквивалентно O(N²) .

Сложность пространства

Игнорируя пространство, необходимое для выходного массива, объемная сложность вышеуказанного алгоритма будет O(N), что требуется для сортировки, если мы не используем алгоритм сортировки на месте.

ПОДРОБНЕЕ:- https://www.golibrary.co/count-all-triplets-with-sum-less-than-target-in-a-given-array/