Algorithm
lc1498_满足条件的子序列数目
思路:
因为是子序列里面最大最小值，子序列可以任意选后面在最大最小范围内数字进入，
所以可以先排序，然后双指针，最后计算子序列数量。
被 nums 为 [1] 和 target 为 1 这个用例 out of bounds 了.
一开始还以为这个用例的答案是1，后面才理解题意的 和 需要就算left，right下标相同时也得是两数相加的值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
impl Solution {
pub fn num_subseq(nums: Vec<i32>, target: i32) -> i32 {
let mut nums = nums;
nums.sort();
let n = nums.len();
let mut left = 0;
let mut right = n - 1;
let mut result = 0;
let mod_val = 1_000_000_007;
// 预计算2的幂次，避免重复计算
let mut pow2 = vec![1; n];
for i in 1..n {
pow2[i] = (pow2[i-1] * 2) % mod_val;
}
while left <= right {
if nums[left] + nums[right] <= target {
// 以left为最小值，right及其左边任意元素为最大值的子序列数量
// 就是从left+1到right这些元素的所有子集数量，即2^(right-left), left必选
result = (result + pow2[right - left]) % mod_val;
left += 1;
} else {
// 避免right为0时减1导致的溢出
if right == 0 {
break;
}
right -= 1;
}
}
result
}
}
|
看题解可知还可以二分查找 right 下标，然后计算子序列数量。
Review
Fragmetric Unlocking Composable Restaking with Solana’s Token-2022 Standard
Tip
Meteora LP Army Bootcamp
Share
fragmetric介绍