1498. Number of Subsequences That Satisfy the Given Sum Condition
给一个 integer array 和 target
找出有几个 subsequences s 满足 min(s) + max(s) <= target 的条件
数量很大所以取模 10^9 + 7
Example 1:
Input: nums = [3,5,6,7], target = 9
Output: 4
Explanation:
有四个 subsequences:
[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:
有六个 subsequences:
[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:
只有两个不符条件 ([6,7], [7]).
所以总共是 63 - 2 = 61 个
思路:
1.一开始看到 mod 10^9 + 7 以为是用 DP
如果说 dp[i] 代表以 nums[i] 当最大值的 subsequences 数量
他的值该怎么找呢 首先这些 subsequences 的 max 都是 nums[i]
所以最小值必须在 target - nums[i] 以下
看到这里好像发现不用 dp 了 可以直接算
dp[i] = (以 i 结尾的 subsequences 数) - (以 i 结尾且都 > target - nums[i])
前面那项就是 2^i (第 0 项到第 i-1 项选与不选)
后面那项可以先二分搜出比 target - nums[i] 大的第一个 nums[j]
然后第 j 项到第 i-1 项选与不选 也就是 2^(i-j)
记得处理一下 j 比 i 大的情况就好
2.因为随着 i 变大 nums[i] 也不断变大 搜到的 nums[j] 只会越来越往左
所以其实可以用 2-pointer 找 j 就好不用每次都 log(n) 搜
然后那个 2^i 蛮让人在意的 可以一开始就先 iterate 0~len(nums)一次算完
也可以直接用 pow(2, i, mod) 哈哈
Python code:
class Solution:
def numSubseq(self, nums: List[int], target: int) -> int:
nums.sort()
n = len(nums)
mod = 10**9+7
pow2 = [1]*n
for i in range(1, n):
pow2[i] = (pow2[i-1] << 1) % mod
j, res = n, 0
for i in range(n):
while j and nums[j-1] > target - nums[i]:
j -= 1
res = (res + pow2[i] - (pow2[i-j] if j <= i else 0)) % mod
return res
3.另外一个做法是算把 nums[i] 当成最小值的 subsequences 数量
这样就变成限制能挑的最大值 一样是能用 2-pointer 做
我觉得写起来比较漂亮 这里就不po了