Skip to content

Latest commit

 

History

History
195 lines (151 loc) · 6.29 KB

1498.md

File metadata and controls

195 lines (151 loc) · 6.29 KB
title description keywords
1498. 满足条件的子序列数目
LeetCode 1498. 满足条件的子序列数目题解，Number of Subsequences That Satisfy the Given Sum Condition，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。
LeetCode
1498. 满足条件的子序列数目
满足条件的子序列数目
Number of Subsequences That Satisfy the Given Sum Condition
解题思路
数组
双指针
二分查找
排序

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

🟠 Medium  🔖  数组 双指针 二分查找 排序  🔗 力扣 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 求出所有子序列的能量和 数组 动态规划 排序 🔴 🀄️ 🔗