Сложность: medium
Дан массив из n целых чисел nums и целое число target. Найдите количество троек индексов i, j, k, удовлетворяющих условию 0 <= i < j < k < n и nums[i] + nums[j] + nums[k] < target.
Пример:
Input: nums = [-2,0,1,3], target = 2
Output: 2
Explanation: Because there are two triplets which sums are less than 2:
[-2,0,1]
[-2,0,3]
👨💻 Алгоритм:
1️⃣Отсортируйте массив nums.
2️⃣Для каждого элемента nums[i] от 0 до n-3 найдите количество пар индексов j и k (где i < j < k), таких что nums[i] + nums[j] + nums[k] < target. Используйте функцию twoSumSmaller, которая ищет количество пар с суммой меньше заданного значения.
3️⃣В функции twoSumSmaller используйте бинарный поиск для поиска верхней границы индекса k и подсчета количества подходящих пар.
😎 Решение:
class Solution {
threeSumSmaller(nums, target) {
nums.sort((a, b) => a - b)
let sum = 0
for (let i = 0; i < nums.length - 2; i++) {
sum += this.twoSumSmaller(nums, i + 1, target - nums[i])
}
return sum
}
twoSumSmaller(nums, startIndex, target) {
let sum = 0
for (let i = startIndex;Ставь 👍 и забирай 📚 Базу знаний