作者JIWP (神楽めあ的錢包)
標題Re: [閒聊] 每日leetcode
時間2025-06-30 01:10:45
1498. Number of Subsequences That Satisfy the Given Sum Condition
思路 :
要找有幾個subsequences符合條件，不用條列出來
所以先將nums依照大小排序
接這用two pointers
左右指標找到nums[L]+nums[R] <= target
在L~R這個範圍內所有跟nums[L]相加都小於target
所以可能的組合有 2^(R-L)
就這樣一直移動R、L直到R<L
就可以得到所有組合
GOLANG CODE :
var mod = 1_000_000_007
func numSubseq(nums []int, target int) int {
slices.Sort(nums)
l, r := 0, len(nums)-1
ans := 0
for r >= l {
for r >= l && nums[r]+nums[l] > target {
r--
}
if l > r {
break
}
ans = ans%mod + pow(r-l)%mod
l++
}
return ans
}
func pow(n int) int {
if n == 0 {
return 1
}
base := 2
res := 1
for n > 0 {
if n&1 == 1 {
res = res * base % mod
}
base = base * base % mod
n /= 2
}
return res% mod
}
--
https://i.imgur.com/r9FBAGO.gif
--
※ 發信站: 批踢踢實業坊(ptt-web.org.tw), 來自: 203.121.235.241 (臺灣)
※ 文章網址: https://ptt-web.org.tw/Marginalman/M.1751217050.A.E61