Leetcode:1498. Number of subsequences that meet the conditions [sort + bisection + power hash table]

analysis

Subsequence should be maximum and minimum , In fact, it doesn't matter if you sort
Fixed the smallest , You can find the largest
Then the middle option is optional
So there is 2 The power of
And then in order to accelerate ,2 To hash and save
Don't count every time

ac code

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        MOD = 10 ** 9 + 7
        n = len(nums)
        nums.sort()

        #  Hash computing power memory 
        f = [1] * (n + 1)
        for i in range(1, n + 1):
            f[i] = f[i - 1] * 2 % MOD


        #  Fix the smallest 
        ans = 0
        for i in range(n):
            minn = nums[i]
            maxn = target - minn
            if maxn < minn:
                break
            idx = bisect_right(nums, maxn) - 1
            if idx >= i:
                ans += f[idx - i]
                ans %= MOD
        
        return ans

summary

Hash memory power acceleration