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了