Задача: 259. 3Sum Smaller
Сложность: 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 {
    func threeSumSmaller(_ nums: [Int], _ target: Int) -> Int {
        let nums = nums.sorted()
        var sum = 0
        for i in 0..<nums.count - 2 {
            sum += twoSumSmaller(nums, i + 1, target - nums[i])
        }
        return sum
    }

    private func twoSumSmaller(_ nums: [Int], _ startIndex: Int, _ target: Int) -> Int {
        var sum = 0
        for i in startIndex..<nums.count - 1 {
            let j = binarySearch(nums, i, target - nums[i])
            sum += j - i
        }
        return sum
    }

    private func binarySearch(_ nums: [Int], _ startIndex: Int, _ target: Int) -> Int {
        var left = startIndex
        var right = nums.count - 1
        while left < right {
            let mid = (left + right + 1) / 2
            if nums[mid] < target {
                left = mid
            } else {
                right = mid - 1
            }
        }
        return left
    }
}

Ставь 👍 и забирай 📚 Базу знаний