1498. 满足条件的子序列数目

🟠   🔖  数组 双指针 二分查找 排序  🔗 力扣 LeetCode

题目

You are given an array of integers nums and an integer target.

Return _the number ofnon-empty subsequences of _nums such that the sum of the minimum and maximum element on it is less or equal totarget. 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

题目大意

给你一个整数数组 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 个子序列满足该条件。（nums 中可以有重复数字）

[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. 对子序列的性质进行分析：

   • 给定数组 nums，将其按照升序排列，这样可以简化子序列的处理。
   • 假设子序列的最小元素为 nums[i]，最大元素为 nums[j]（i <= j）。
   • 如果 nums[i] + nums[j] <= target，则所有从 nums[i] 到 nums[j] 的子序列都满足条件：
     • 以 nums[i] 为最小元素、以 nums[j] 为最大元素的子序列数为 2^(j - i)（每个位置的元素可选或不选）。

2. 双指针遍历：

   • 使用两个指针 i 和 j，分别指向子序列的最小值和最大值。
   • 初始化 j = nums.length - 1，从最大值开始逐步缩小范围。
   • 如果当前 nums[i] + nums[j] <= target，计算以 nums[i] 为起点的满足条件的子序列数量。
   • 如果条件不满足，减小 j，直到满足为止。

3. 快速计算组合数：

   • 对于每对满足条件的 i 和 j，需要快速计算 2^(j - i)，使用预计算的方式加速：
     • 构造数组 power，其中 power[k] = 2^k % (10^9 + 7)。
     • 查询时可以直接取 power[j - i]。

4. 结果取模：

   • 所有子序列数量加总后对 10^9 + 7 取模，防止结果溢出。

复杂度分析

• 时间复杂度：O(n log n)，排序耗时 O(n log n)，双指针遍历耗时 O(n)，整体时间复杂度为 O(n log n)。

• 空间复杂度：O(n)，预计算数组 power 需要 O(n) 的额外空间。

代码

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var numSubseq = function (nums, target) {
	const MOD = 1e9 + 7;
	nums.sort((a, b) => a - b); // 排序数组

	// 预计算 2^k % MOD
	let power = [1];
	for (let i = 1; i < nums.length; i++) {
		power.push((power[i - 1] * 2) % MOD);
	}

	let i = 0,
		j = nums.length - 1,
		result = 0;

	while (i <= j) {
		if (nums[i] + nums[j] > target) {
			// 缩小最大值
			j--;
		} else {
			// 子序列数目
			result = (result + power[j - i]) % MOD;
			i++; // 增大最小值
		}
	}

	return result;
};

相关题目

题号	标题	题解	标签	难度	力扣
2835	使子序列的和等于目标的最少操作次数		贪心 位运算 数组	🔴	🀄️ 🔗
3082	求出所有子序列的能量和		数组 动态规划	🔴	🀄️ 🔗
3098	求出所有子序列的能量和		数组 动态规划 排序	🔴	🀄️ 🔗