Medium

题目描述

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

请你返回 nums 中能满足其中最小值和最大值的和小于等于 target 的 非空 子序列的数目。由于答案可能很大，请将结果对 10^9 + 7 取模后返回。

示例 1：

输入：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)

示例 2：

输入：nums = [3,3,6,8], target = 10
输出：6
解释：有 6 个子序列满足该条件。
[3] , [3] , [3,3], [3,6] , [3,6] , [3,3,6]

示例 3：

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

提示：

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

解题思路

这道题的关键观察是：子序列的最小值和最大值只与其边界元素有关。因此我们可以先对数组排序，这样便于确定最小值和最大值。

核心思路：

  1. 对数组进行排序，这样任何子序列的最小值就是其最左边的元素，最大值就是最右边的元素
  2. 使用双指针技巧：左指针 left 指向当前考虑的最小值，右指针 right 寻找满足条件的最大值位置
  3. 对于固定的左端点 left，如果 nums[left] + nums[right] <= target，那么所有以 nums[left] 为最小值、以 nums[left] 到 nums[right] 之间任意元素为最大值的子序列都满足条件
  4. 关键计算：以 nums[left] 为最小值的满足条件的子序列个数为 2^(right-left)，因为 nums[left+1] 到 nums[right] 的每个元素都可以选择包含或不包含

算法步骤：

  1. 排序数组
  2. 预计算 2 的幂次方数组，避免重复计算
  3. 使用双指针遍历，累加满足条件的子序列数量

时间复杂度主要来自排序，双指针遍历是线性的。

代码实现

class Solution {
public:
    int numSubseq(vector<int>& nums, int target) {
        const int MOD = 1e9 + 7;
        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 left = 0, right = n - 1;
        int result = 0;
        
        while (left <= right) {
            if (nums[left] + nums[right] <= target) {
                result = (result + power[right - left]) % MOD;
                left++;
            } else {
                right--;
            }
        }
        
        return result;
    }
};

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        MOD = 10**9 + 7
        nums.sort()
        
        n = len(nums)
        power = [1] * n
        for i in range(1, n):
            power[i] = (power[i-1] * 2) % MOD
        
        left, right = 0, n - 1
        result = 0
        
        while left <= right:
            if nums[left] + nums[right] <= target:
                result = (result + power[right - left]) % MOD
                left += 1
            else:
                right -= 1
        
        return result

public class Solution {
    public int NumSubseq(int[] nums, int target) {
        const int MOD = 1000000007;
        Array.Sort(nums);
        
        int n = nums.Length;
        int[] power = new int[n];
        power[0] = 1;
        for (int i = 1; i < n; i++) {
            power[i] = (int)((long)power[i-1] * 2 % MOD);
        }
        
        int left = 0, right = n - 1;
        int result = 0;
        
        while (left <= right) {
            if (nums[left] + nums[right] <= target) {
                result = (int)((result + power[right - left]) % MOD);
                left++;
            } else {
                right--;
            }
        }
        
        return result;
    }
}

var numSubseq = function(nums, target) {
    const MOD = 1e9 + 7;
    nums.sort((a, b) => a - b);
    
    const n = nums.length;
    const power = new Array(n);
    power[0] = 1;
    for (let i = 1; i < n; i++) {
        power[i] = (power[i-1] * 2) % MOD;
    }
    
    let left = 0, right = n - 1;
    let result = 0;
    
    while (left <= right) {
        if (nums[left] + nums[right] <= target) {
            result = (result + power[right - left]) % MOD;
            left++;
        } else {
            right--;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)主要来自数组排序，双指针遍历为 O(n)
空间复杂度O(n)存储 2 的幂次方数组

相关题目