题目描述

给你一个整数数组 nums 和一个整数 target。

请你统计并返回 nums 中能满足其最小元素与最大元素的 和 小于或等于 target 的 非空 子序列的数目。

由于答案可能很大，请将结果对 10^9 + 7 取余后返回。

样例

输入：nums = [3,5,6,7], target = 9
输出：4
解释：有 4 个子序列满足该条件。
[3] -> 最小元素 + 最大元素 <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)

输入：nums = [3,3,6,8], target = 10
输出：6
解释：有 6 个子序列满足该条件。（nums 中可以有重复数字）
[3] , [3] , [3,3], [3,6] , [3,6] , [3,3,6]

输入：nums = [2,3,3,4,6,7], target = 12
输出：61
解释：共有 63 个非空子序列，其中 2 个不满足条件（[6,7], [7]）
有效序列总数为（63 - 2 = 61）

输入：nums = [5,2,4,1,7,6,8], target = 16
输出：127
解释：所有非空子序列都满足条件 (2^7 - 1) = 127

限制

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

算法1

(二分) $O(n \log n)$

1. 将数组从小到大排序。对于每个位置 $i$，二分查询最小的位置 $l \ge i$，满足 $nums(i) + nums(l) > target$。如果 $m$ 不存在则令 $l := n$。
2. 对于最小值 $nums(i)$，我们可选的最大值有 $nums(i)$，$nums(i + 1)$ 一直到 $nums(l - 1)$。
3. 如果 $l > i$，则可选的方案数为 $1 + 2^0 + \dots + 2^{l - i - 2} = 2^{l - i - 1}$。

时间复杂度

• 排序的时间复杂度为 $O(n \log n)$。
• 对于每个位置，二分的时间复杂度为 $O(\log n)$。
• 故总时间复杂度为 $O(n \log n)$。

空间复杂度

• 需要额外 $O(n)$ 的空间存储预处理的 2 的幂次。

C++ 代码

class Solution {
public:
    int numSubseq(vector<int>& nums, int target) {
        const int mod = 1000000007;

        sort(nums.begin(), nums.end());

        int n = nums.size();

        vector<int> power(n);
        power[0] = 1;

        for (int i = 1; i < n; i++)
            power[i] = power[i - 1] * 2 % mod;

        int ans = 0;
        for (int i = 0; i < n; i++) {
            int l = i, r = n;
            while (l < r) {
                int mid = (l + r) >> 1;
                if (nums[i] + nums[mid] <= target)
                    l = mid + 1;
                else
                    r = mid;
            }

            if (l > i)
                ans = (ans + power[l - i - 1]) % mod;
        }

        return ans;
    }
};

算法2

(双指针) $O(n)$

1. 将数组从小到大排序。
2. 仿照 Two Sum 的双指针解法，初始时固定 $l := 0$，$r := n - 1$。
3. 在 $l \le r$ 的情况下，如果 $nums(l) + nums(r) \le target$，则 $l$ 自加。否则 $r$ 自减。
4. 注意到，当 $nums(l) + nums(r) \le target$ 成立时，对于 $nums(l)$ 来说，$nums(r)$ 是最大可选的最大值。
5. 也就是说对于最小值 $nums(l)$，可选的最大值有 $nums(l)$，$nums(l + 1)$ 一直到 $nums(r)$。
6. 故可选的方案数为 $1 + 2^0 + 2^1 + \dots + 2^{r - l - 1} = 2^{r - l}$。

时间复杂度

• 排序的时间复杂度为 $O(n \log n)$。
• 排序后双指针每个位置仅被遍历一次。
• 故总时间复杂度为 $O(n \log n)$。

空间复杂度

• 需要额外 $O(n)$ 的空间存储预处理的 2 的幂次。

C++ 代码

class Solution {
public:
    int numSubseq(vector<int>& nums, int target) {
        const int mod = 1000000007;

        sort(nums.begin(), nums.end());

        int n = nums.size();
        vector<int> power(n);

        power[0] = 1;
        for (int i = 1; i < n; i++)
            power[i] = power[i - 1] * 2 % mod;

        int ans = 0;
        int l = 0, r = n - 1;

        while (l <= r) {
            if (nums[l] + nums[r] <= target) {
                ans = (ans + power[r - l]) % mod;
                l++;
            } else {
                r--;
            }
        }

        return ans;
    }
};