Leetcode 1498. Number of Subsequences That Satisfy the Given Sum Condition (python)

题目

解法：

解析见注释

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        # main idea: sort the nums first. Then we can search for low bound and upper bound and count. For a fixed lower bound, we find the most right upper bound which satisfy the condition. With fixed lower bound, all sub sequence in the range[lower,upper] satisfy the condition. The number of sub sequence can be calculated by 2^(upper -lower). for example [3,5,6], with 3 fixed as the lower bound, all subsequence can be [3],[3,5],[3,5,6],[3,6]. The ocunt equals 2^(2-0). And we can move the lower bound towards right and find new upper bounds by moving towards left. Because the calculation to power n is actually O(n)， so we store the powers ahead of time
        n = len(nums)
        powers = [0]*n
        powers[0] = 1
        tmp = 1
        # store the powers of 2 ahead of time to prevent repeat calculation
        for i in range(1,n):
            tmp*=2
            powers[i] = tmp
        
        nums.sort()
        ans = 0
        right = n
        # enumerate the lower bound
        for left in range(n):
            # if the lower bound it self cannot be a valid sub sequence, it means no more valid sub sequence can be formed after this position
            if 2*nums[left]>target:
                break
            # for a fixed lower bound, we move the upper bound towards left to find all the satisfied upper bounds for this fixed lower bounds   
            while right>=n or (right < n and nums[right]+nums[left]>target):
                right -= 1
            ans += powers[right-left]
        return ans%(10**9+7)