alighters

程序、写作、人生

1498. Number of Subsequences That Satisfy the Given Sum Condition

| Comments

具体链接： https://leetcode-cn.com/problems/number-of-subsequences-that-satisfy-the-given-sum-condition/

思路

因题意中，不要求数组的连续，只需要求相应的组合即可。

所以，这里可以先进行数组的排序。 遍历当前的数组，以当前数为基准，求 target - nums[i] 的值，在数组中，所处于的 Index 值。（可通过 bisect.bisect 的二分求解来得到此值。）

当得到此 index 值，以包含当前 nums[i] ，来求一个可以的组合数。其选择的方案为从 i + 1 至 index 的数，可选或者不选，一共的组合数为：

1

2 ** (index - i - 1)

所以，最后的结果数，就是将这些结果累加即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

from typing import List


class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        ans = 0
        import bisect
        for i, num in enumerate(nums):
            if num * 2 <= target:
                index = bisect.bisect(nums, target - num, i)
                if index > i:
                    ans += 2 ** (index - i - 1)
            else:
                break
        return ans % (10 ** 9 + 7)

注意事项

在其他语言中，因求这个 2 的幂数，会存在溢出或者超时的情况。所以，都会使用预计算，这些 2 的幂数的结果。方便后续的加速求值。

版权归作者所有，转载请注明原文链接：/blog/2020/09/13/1498-number-of-subsequences-that-satisfy-the-given-sum-condition/

给 Ta 个打赏吧...

Comments