[binary search - medium] 1498 Number of subsequences satisfying the condition

subject
Be careful ：

1. The topic is to calculate the number of subsequences
   Here we need to clarify a concept , A subsequence is a non continuous sequence of elements in the original sequence , Suppose you have a sequence [1,2,3,4,5,6] be [1,2,3],[1,5,6] Are all subsequences of the original sequence
2. Program input sequence nums Is chaotic , You can do it first nums Sort and then operate , It has no effect on the results , But it can simplify the program code

【 Code 】 Double pointer
Execution time ：7380 ms, In all Python3 Defeated in submission 27.50% Users of
Memory consumption ：24.6 MB, In all Python3 Defeated in submission 50.00% Users of
Pass the test case ：62 / 62

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        left,right=0,len(nums)-1
        ans=0
        while left<=right:
            if nums[left]+nums[right]<=target:
                ans+=2**(right-left)
                left+=1
            else:
                right-=1
        return ans%(1000000007)              

【 Method 2】 Dichotomy
Execution time ：7992 ms, In all Python3 Defeated in submission 14.17% Users of
Memory consumption ：24.9 MB, In all Python3 Defeated in submission 5.83% Users of
Pass the test case ：62 / 62

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        n = len(nums)
        P = 10**9 + 7
        nums.sort()
        ans = 0
        for i, num in enumerate(nums):
            if nums[i] * 2 > target:
                break
            maxValue = target - nums[i]
            pos=-1
            left,right=i,n-1
            while left<=right:
                mid=left+(right-left)//2
                if nums[mid]<=(target-num):
                    pos=mid
                    left=mid+1
                else:
                    right=mid-1
            contribute = 2**(pos - i) if pos >= i else 0
            ans += contribute
        
        return ans % P

【 Method 2 The accelerated version of 】
Execution time ：580 ms, In all Python3 Defeated in submission 58.33% Users of
Memory consumption ：24.5 MB, In all Python3 Defeated in submission 69.17% Users of
Pass the test case ：62 / 62

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        n = len(nums)
        P = 10**9 + 7
        nums.sort()
        ans = 0
        f = [1] + [0] * (n - 1)
        for i in range(1, n):
            f[i] = f[i - 1] * 2 % P
        for i, num in enumerate(nums):
            if nums[i] * 2 > target:
                break
            maxValue = target - nums[i]
            pos=-1
            left,right=i,n-1
            while left<=right:
                mid=left+(right-left)//2
                if nums[mid]<=(target-num):
                    pos=mid
                    left=mid+1
                else:
                    right=mid-1
            contribute = f[pos - i] if pos >= i else 0
            ans += contribute
        
        return ans % P

【 Method 3】 Two points
Execution time ：220 ms, In all Python3 Defeated in submission 95.83% Users of
Memory consumption ：24.5 MB, In all Python3 Defeated in submission 70.83% Users of
Pass the test case ：62 / 62

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        n = len(nums)
        P = 10**9 + 7
        f = [1] + [0] * (n - 1)
        # print(f)
        for i in range(1, n):
            f[i] = f[i - 1] * 2 % P
        # print(f)

        nums.sort()
        ans = 0
        for i, num in enumerate(nums):
            if nums[i] * 2 > target:
                break
            maxValue = target - nums[i]
            pos = bisect.bisect_right(nums, maxValue) - 1
            # print("maxValue:",maxValue," pos:",pos,' i:',i)
            contribute = f[pos - i] if pos >= i else 0
            # print(contribute)
            ans += contribute
        
        return ans % P