class Solution {
public:
int numSubseq(vector<int>& nums, int target) {
}
};
1498. 满足条件的子序列数目
给你一个整数数组 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原站题解
golang 解法, 执行用时: 124 ms, 内存消耗: 7.6 MB, 提交时间: 2023-09-11 16:25:22
// 双指针
func numSubseq2(nums []int, target int) int {
sort.Ints(nums)
dp := make([]int, len(nums))
dp[0] = 1
for i := 1; i < len(dp); i++ {
dp[i] = dp[i-1] * 2 % (1e9 + 7) // 表示长度为i时，组合个数，比如长度2的数组，组合个数为4
}
l, r, res := 0, len(nums)-1, 0
for l < r {
tmp := nums[l] + nums[r]
if tmp <= target {
res = (res + dp[r-l]) % (1e9 + 7) //表示以l为左边界，l+1至r之间任一数字作为右边界，都满足上述条件，共计组合个数
l += 1
} else {
r -= 1
}
}
return res
}
/*
二分法
*/
func numSubseq(nums []int, target int) int {
sort.Ints(nums)
dp := make([]int, len(nums))
dp[0] = 1
res := 0
for i := 1; i < len(dp); i++ {
dp[i] = dp[i-1] * 2 % (1e9 + 7) // 表示长度为i时，组合个数，比如长度2的数组，组合个数为4
}
for i := 0; i < len(nums) && nums[i]*2 <= target; i++ { // 确定左边界，二分法查找右边界的最大索引
max := target - nums[i]
l, r := i+1, len(nums)-1
for l <= r {
mid := l + (r-l)>>1
if nums[mid] <= max {
l = mid + 1
} else {
r = mid - 1
}
}
//if l >= len(nums) || nums[l] > max {
// l -= 1
//}
if r-i >= 0 {
res = (res + dp[r-i]) % (1e9 + 7)
}
}
return res
}
python3 解法, 执行用时: 8388 ms, 内存消耗: 26.6 MB, 提交时间: 2023-09-11 16:23:07
class Solution:
def numSubseq(self, nums: List[int], target: int) -> int:
nums.sort()
if nums[0] * 2 > target:
return 0
left = 0
right = len(nums) - 1
res = 0
while left <= right:
if nums[left] + nums[right] <= target:
res += 2**(right-left)
left += 1
else:
right -= 1
return res%(10**9+7)
python3 解法, 执行用时: 276 ms, 内存消耗: 26.5 MB, 提交时间: 2023-09-11 16:05:30
'''
计算贡献值
预处理2^i mod (1e9 +7) 的值，然后原序列排序。枚举所有合法的Vmin,
对每个Vmin，二分查找出Vmax，Vmin和Vmax最大值下标的差绝对值x, 当前贡献就是2^(x-1)
'''
class Solution:
def numSubseq(self, nums: List[int], target: int) -> int:
n = len(nums)
P = 10**9 + 7
f = [1] + [0] * (n - 1)
for i in range(1, n):
f[i] = f[i - 1] * 2 % P
nums.sort()
ans = 0
for i, num in enumerate(nums):
if nums[i] * 2 > target:
break
maxValue = target - nums[i]
pos = bisect.bisect_right(nums, maxValue) - 1
contribute = f[pos - i] if pos >= i else 0
ans += contribute
return ans % P