LeetCode 题解工作台
满足条件的子序列数目
给你一个整数数组 nums 和一个整数 target 。 请你统计并返回 nums 中能满足其最小元素与最大元素的 和 小于或等于 target 的 非空 子序列的数目。 由于答案可能很大，请将结果对 10 9 + 7 取余后返回。 示例 1： 输入： nums = [3,5,6,7], targe…
4
题型
6
代码语言
3
相关题
当前训练重点
中等 · 二分·搜索·答案·空间
答案摘要
由于题目中描述的是子序列，并且涉及到最小元素与最大元素的和，因此我们可以先对数组 进行排序。 然后我们枚举最小元素 ，对于每个 ，我们可以在 $\textit{nums}[i + 1]$ 到 $\textit{nums}[n - 1]$ 中找到最大元素 ，使得 $\textit{nums}[i] + \textit{nums}[j] \leq \textit{target}$，此时满足条件的子序…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·搜索·答案·空间 题型思路
题目描述
给你一个整数数组 nums 和一个整数 target 。
请你统计并返回 nums 中能满足其最小元素与最大元素的 和 小于或等于 target 的 非空 子序列的数目。
由于答案可能很大，请将结果对 109 + 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 <= 1051 <= nums[i] <= 1061 <= target <= 106
解题思路
方法一：排序 + 二分查找
由于题目中描述的是子序列，并且涉及到最小元素与最大元素的和，因此我们可以先对数组 进行排序。
然后我们枚举最小元素 ，对于每个 ，我们可以在 到 中找到最大元素 ，使得 ，此时满足条件的子序列数目为 ，其中 表示从 到 的所有子序列的数目。我们将所有的子序列数目累加即可。
时间复杂度 ，空间复杂度 。其中 为数组 的长度。
class Solution:
def numSubseq(self, nums: List[int], target: int) -> int:
mod = 10**9 + 7
nums.sort()
n = len(nums)
f = [1] + [0] * n
for i in range(1, n + 1):
f[i] = f[i - 1] * 2 % mod
ans = 0
for i, x in enumerate(nums):
if x * 2 > target:
break
j = bisect_right(nums, target - x, i + 1) - 1
ans = (ans + f[j - i]) % mod
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Check if candidate sorts the array before counting subsequences.
- question_mark
See if candidate uses two pointers instead of nested loops to optimize performance.
- question_mark
Watch for correct modular arithmetic to handle large counts.
常见陷阱
外企场景- error
Forgetting to include subsequences of length one, which are valid by definition.
- error
Failing to handle repeated numbers correctly when counting combinations.
- error
Not applying modulo at each step, leading to integer overflow.
进阶变体
外企场景- arrow_right_alt
Count subsequences where the difference between max and min is at most target instead of sum.
- arrow_right_alt
Find subsequences of exactly k elements satisfying min + max ≤ target.
- arrow_right_alt
Compute the sum of all valid subsequences modulo 10^9 + 7 rather than counting them.