Задача: 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. 😎 Решение: class Solution: def numSubseq(self, nums: List[int], target: int) -> int: nums.sort() n = len(nums) mod = 10**9 + 7 power = [1] n for i in range(1, n): power[i] = power[i - 1] 2 % mod answer = 0 left, right = 0, n - 1 while left <= right: if nums[left] + nums[right] <= target: answer = (answer + power[right - left]) % mod left += 1 else: right -= 1 return answer Ставь 👍 и забирай 📚 Базу знаний