1498.Number of Subsequences That Satisfy the Given Sum Condition

Tags: Sort Two Pointers Medium

Links: 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

---

这道题思路非常类似于求数组内可以组成三角形边的三元组的个数（LeetCode 611），先将数组排序（之所以可以排序求解，是因为并未要求子数组连续），left, right分别指向数组首尾，如果满足首尾之和不超过target，那么意味着从left + 1到right这些数字都存在两种选择（选和不选，left指向的数字必选），那么就存在$2^{\text{right} - \text{left}}$种选择，需要注意right - left的值可能很大，这种情况下的幂运算取模就变成了《算法竞赛进阶指南》里面0x01的a^b问题，采用快速幂求解。

时间复杂度$O(n \log n)$。

class Solution {
    static constexpr long long M = 1e9 + 7;
public:
    int numSubseq(vector<int>& nums, int target) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int n = nums.size(), left = 0, right = n - 1;
        sort(nums.begin(), nums.end());
        long long res = 0;

        while (left <= right) {
            while (left <= right && nums[left] + nums[right] > target) --right;

            if (left > right) break;

            res = (res + myPow(2, right - left)) % M;
            ++left;
        }

        return res;
    }

    long long myPow(long long base, int exp)
    {
        long long res = 1;
        while (exp) {
            if (exp & 1) res = res * base % M;
            base = base * base % M;
            exp >>= 1;
        }

        return res;
    }
};