05 August 2008
满足条件的子序列数目
给一个整数数组 nums 和一个整数 target 。
统计并返回 nums 中能满足其最小元素与最大元素的 和 小于或等于 target 的 非空 子序列的数目。
由于答案可能很大，请将结果对 10^9 + 7 取余后返回。
双指针 + 排序
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
class Solution {
public int numSubseq(int[] nums, int target) {
// 1. 预处理2的n次方
int MOD = (int)1e9 + 7, n = nums.length;
int[] f = new int[n];
f[0] = 1;
for (int i = 1; i < f.length; ++i) {
f[i] = (f[i - 1] << 1) % MOD;
}
// 2. 双指针l和r表示最小元素和最大元素下标
// 例如l为1，r为5，则l的右边有5-1=4个元素，以l为最小元素的子序列，就是这4个元素的子集，共有2的4次方个
Arrays.sort(nums);
int l = 0, r = n - 1;
long ans = 0;
while (l <= r) {
int sum = nums[l] + nums[r];
if (sum > target) {
r--;
} else {
ans = (ans + f[r - l]) % MOD;
l++;
}
}
return (int)((ans + MOD) % MOD);
}
}
这一题只需要统计子序列的个数，其实并没有用到任何子序列的顺序关系，与其说是统计子序列，不如说是统计不同的子集个数。 我相信如果题目叙述改成统计子集个数，我会第一时间想到排序，但是子序列这个说法确实迷惑了我。感觉还是因为这种类型问题做太少了，对于这种东西理解不够深。
想到排序，这题就非常简单了，从最小的数min开始，做一个二分搜索找到最大的满足max + min <= target的数max，那么，min到max之间所有的子集都是满足要求的。个数为2 ^ (maxIdx - minIdx). 有个细节就是要把2的幂次的计算结果存起来因为会溢出。
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
class Solution {
private static final long MOD = 1000000007;
public int numSubseq(int[] nums, int target) {
long ans = 0;
Arrays.sort(nums);
long[] rs = new long[nums.length];
rs[0] = 1;
for (int i = 1; i < nums.length; ++i) {
rs[i] = (rs[i - 1] << 1) % MOD;
}
for (int i = 0; i < nums.length; ++i) {
int l = i;
int r = nums.length;
while (r - l > 1) {
int mid = l + (r - l) / 2;
if (nums[mid] + nums[i] <= target) {
l = mid;
} else {
r = mid;
}
}
if (nums[l] + nums[i] <= target) {
ans = (ans + rs[l - i]) % MOD;
}
}
return (int) ans;
}
}