Сложность: 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
Ставь 👍 и забирай 📚 Базу знаний