1498. Количество подпоследовательностей, удовлетворяющих заданному условию суммы | Ежедневное зад...

ПРИМЕЧАНИЕ: Мы рассматриваем только подпоследовательности, содержащие leftPointer. Таким образом, для допустимой последовательности [1,2,3] мы рассматриваем все подпоследовательности, содержащие leftPointer с номером 1, такие как {1}, {1,2}, {1,3}, {1,2,3}, но не {2} или {2,3}. Поскольку могут быть крайние случаи, например, [1,3,3] является допустимой последовательностью, тогда как [3] или [3,3] не являются допустимыми (целевое значение = 5), если мы рассматриваем все подпоследовательности. Поэтому мы учитываем только количество подпоследовательностей, содержащих leftPointer. Кроме того, для любой последовательности длиной 3, например [1,2,3], у нас есть варианты формирования допустимых подпоследовательностей: 1 2 3 ✅ ✅ ✅ {1,2,3} ✅ ✅ ❌ {1,2} ✅ ❌ ✅ {1,3} ✅ ❌ ❌ {1} Каждое число имеет два варианта: включить или исключить. Таким образом, общее количество допустимых подпоследовательностей можно легко вычислить, взяв 2^(j-i) https://leetcode.com/problems/number-of-subsequences-that-satisfy-the-given-sum-condition/description/ Похожие задачи LC: 696. Подсчет двоичных подстрок 713. Произведение подмассивов меньше K 930. Двоичные подмассивы с суммой 992. Подмассивы с K различными целыми числами 1358. Количество подстрок, содержащих все три символа 1513. Количество подстрок, содержащих только единицы 1839. Самая длинная подстрока из всех гласных в порядке возрастания 2062. Подсчет гласных подстрок строки 2063. Гласные во всех подстроках 0:00 - Понимание вопроса 3:45 - Интуиция 11:10 - Подход 12:40 - Код 16:40 - Сложность #coding #dsa #leetcode #daily #programming #cpp #tutorial