1498. Number of Subsequences That Satisfy the Given Sum Condition
Medium
You are given an array of integers
nums
and an integer target
.Return the number of non-empty subsequences of
nums
such that the sum of the minimum and maximum element on it is less or equal to target
. Since the answer may be too large, return it modulo 109 + 7
.Example 1:
Input: nums = [3,5,6,7], target = 9
Output: 4
Explanation: There are 4 subsequences that satisfy the condition.
[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: There are 6 subsequences that satisfy the condition. (nums can have repeated numbers).
[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: There are 63 non-empty subsequences, two of them do not satisfy the condition ([6,7], [7]).
Number of valid subsequences (63 - 2 = 61).
Constraints:
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^6
1 <= target <= 10^6
這題 一直過不了,後來發現是直接使用
math.Pow(float64(x), float64(y))
的話會 overflow!可以執行下面程式看看,會發現到某個數之後,印出來的都是 -9223372036854775808
package main
import (
"fmt"
"math"
)
func main() {
for i := 0; i < 10000; i++ { //題目 nums 長度最大 10000
fmt.Println(powInt(2, i))
}
}
func powInt(x, y int) int {
return int(math.Pow(float64(x), float64(y)))
}
func numSubseq(nums []int, target int) int {
sort.Ints(nums)
left, right := 0, len(nums)-1
ans := 0
pow2 := make([]int, len(nums)+1)
pow2[0] = 1
for i := 1; i <= len(nums); i++ {
pow2[i] = (pow2[i-1] * 2) % 1000000007
}
for left <= right {
if nums[left] + nums[right] <= target {
ans += pow2[right-left]
left++
} else {
right--
}
}
return ans % 1000000007
}