1498. Number of Subsequences That Satisfy the Given Sum Condition

https://leetcode.com/problems/number-of-subsequences-that-satisfy-the-given-sum-condition/

Given an array of integers nums and an integer target.

Return the number of non-empty subsequences of nums such that the sum of the minimum and maximum element on it is less or equal than target.

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

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)

Example 2:

Input: nums = [3,3,6,8], target = 10
Output: 6
Explanation: There are 6 subsequences that satisfy the condition. (nums can have repeated numbers).
[3] , [3] , [3,3], [3,6] , [3,6] , [3,3,6]

Example 3:

Input: nums = [2,3,3,4,6,7], target = 12
Output: 61
Explanation: There are 63 non-empty subsequences, two of them don't satisfy the condition ([6,7], [7]).
Number of valid subsequences (63 - 2 = 61).

Example 4:

Input: nums = [5,2,4,1,7,6,8], target = 16
Output: 127
Explanation: All non-empty subset satisfy the condition (2^7 - 1) = 127

Constraints:

• 1 <= nums.length <= 10^5

• 1 <= nums[i] <= 10^6

• 1 <= target <= 10^6

给定数组统计满足其中最大元素和最大元素的和小于等于target的子集合数目。不断且快速找最大最小 => 先sorting。sorting后观察到如果[l, r]满足l + r <= target，那么l, r之间的任意组合都满足，无需遍历[l, r - 1]，一共pow(2, r - l)个，l++；且如果[l, r]不满足，[l + 1, r]都不会满足，r-- => 双指针。重复计算2 ** (r - l) % M耗时过多，提前记录pow取值以复用。

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort() 
        M, N = 1000000007, len(nums)
        l, r, res = 0, N - 1, 0
        pow = [1] * N
        for i in range(1, N):
            pow[i] = pow[i - 1] * 2 % M
        # pow = [2 ** i % M for i in range(len(nums))]
        while l <= r:
            if nums[l] + nums[r] <= target:
                # res = (res % M + 2 ** (r - l) % M) % M 
                # res += pow(2, r - l, M)
                res = (res + pow[r - l]) % M
                l += 1
            else:
                r -= 1
        return res