Home Coding Leetcode Medium

⭐️⭐️

# 題目敘述

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).

# Solution



import java.util.Arrays;
class Solution {
    public int numSubseq(int[] nums, int target) {
        int n = nums.length;
        int mod = 1000000007;
        int ans = 0;
        Arrays.sort(nums);
        int[] count = new int[n];
        count[0] = 1;
        for (int i = 1; i < n; i++) {
            count[i] = (count[i - 1] * 2) % mod;
        }
        int left = 0, right = n - 1;
        while (left <= right) {
            if (nums[left] + nums[right] <= target) {
                ans = (ans + count[right - left]) % mod;
                left++;
            } else {
                right--;
            }
        }
        
        return ans;
    }
}