1498.Number of Subsequences That Satisfy the Given Sum Condition
===

###### tags: `Medium`,`Array`,`Two Pointers`,`Binary Search`,`Sorting`

[1498. Number of Subsequences That Satisfy the Given Sum Condition](https://leetcode.com/problems/number-of-subsequences-that-satisfy-the-given-sum-condition/)

### 題目描述

You are 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 to* `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 do not satisfy the condition ([6,7], [7]).
Number of valid subsequences (63 - 2 = 61).

**Constraints**:

* 1 <= `nums.length` <= 10^5^
* 1 <= `nums[i]` <= 10^6^
* 1 <= `target` <= 10^6^

### 解答
#### Python

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

        ans = 0
        l, r = 0, n - 1
        while l <= r:
            if nums[l] + nums[r] <= target:
                ans = (ans + pow(2, r - l, MOD)) % MOD
                l += 1
            else:
                r -= 1
        return ans

> [name=Yen-Chi Chen][time=Sun, May 7, 2023]

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()

        ans = 0
        l, r = 0, len(nums) - 1
        while l <= r:
            ans <<= 1
            if nums[l] + nums[r] <= target:
                ans += 1
                l += 1
            else:
                r -= 1
        return ans % (10 ** 9 + 7)

> [name=Yen-Chi Chen][time=Sun, May 7, 2023]

#### Javascript

function numSubseq(nums, target) {
  nums.sort((a, b) => a - b);
  let count = 0;
  let left = 0;
  let right = nums.length - 1;
  const mod = 1e9 + 7;

  const pow2 = new Array(nums.length).fill(0);
  pow2[0] = 1;
  for (let i = 1; i < nums.length; i++) {
    pow2[i] = (pow2[i - 1] * 2) % mod;
  }

  while (left <= right) {
    if (nums[left] + nums[right] > target) {
      right--;
    } else {
      count = (count + pow2[right - left]) % mod;
      left++;
    }
  }

  return count;
}

> [name=Marsgoat][time=Sun, May 7, 2023]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)