Задача: 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 и подсчета количества подходящих пар.

😎 Решение:

import java.util.Arrays;

class Solution {
    public int threeSumSmaller(int[] nums, int target) {
        Arrays.sort(nums);
        int sum = 0;
        for (int i = 0; i < nums.length - 2; i++) {
            sum += twoSumSmaller(nums, i + 1, target - nums[i]);
        }
        return sum;
    }

    private int twoSumSmaller(int[] nums, int startIndex, int target) {
        int sum = 0;
        for (int i = startIndex; i < nums.length - 1; i++) {
            int j = binarySearch(nums, i, target - nums[i]);
            sum += j - i;
        }
        return sum;
    }

    private int binarySearch(int[] nums, int startIndex, int target) {
        int left = startIndex;
        int right = nums.length - 1;
        while (left < right) {
            int mid = (left + right + 1) / 2;
            if (nums[mid] < target) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}

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