Задача: 1498. Number of Subsequences That Satisfy the Given Sum Condition
Сложность: medium

Вам дан массив целых чисел nums и целое число target.

Верните количество непустых подпоследовательностей массива nums, таких что сумма минимального и максимального элемента в них меньше или равна target. Так как ответ может быть слишком большим, верните его по модулю 10^9 + 7.

Пример:

Input: nums = [3,5,6,7], target = 9
Output: 4
Explanation: There are 4 subsequences that satisfy the condition.
[3] -> Min value + max value <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)

👨‍💻 Алгоритм:

1⃣Инициализация и подготовка:
Инициализируйте переменные answer равным 0 и n как длину массива nums.
Отсортируйте массив nums.
Подготовьте массив power для хранения степеней двойки до n по модулю 10^9+7.

2⃣Итерация и бинарный поиск:
Для каждого индекса left от 0 до n - 1 выполните бинарный поиск, чтобы найти самый правый индекс right, где nums[right] <= target - nums[left].
Если left <= right, добавьте количество допустимых подпоследовательностей к answer.

3⃣Возврат результата:
Верните answer по модулю 10^9+7.

😎 Решение:

var numSubseq = function(nums, target) {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    const mod = 1_000_000_007;
    
    const power = new Array(n).fill(1);
    for (let i = 1; i < n; i++) {
        power[i] = (power[i - 1] * 2) % mod;
    }
    
    let answer = 0;
    let left = 0, right = n - 1;
    
    while (left <= right) {
        if (nums[left] + nums[right] <= target) {
            answer = (answer + power[right - left]) % mod;
            left++;
        } else {
            right--;
        }
    }
    
    return answer;
};

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