1498. Number of Subsequences That Satisfy the Given Sum Condition

https://leetcode.com/problems/number-of-subsequences-that-satisfy-the-given-sum-condition/

第一次看到这题时,直觉告诉我觉得肯定不能对 nums 做排序。通常子序列的问题涉及到元素顺序,一般是不会对输入数据做排序的。

我最开始的想法是这样的:

我觉得这个想法非常巧妙,不过可惜是错误的,因为x可能作为最小值存在。当然可以再上面那个算法的基础上稍加修补,不过代码就会很复杂。 另外查询的时间复杂度也会比较高,最坏情况下面会是O(n).


仔细想想,其实完全可以对 nums 做排序,然后使用双指针i, j来遍历:

除此之外还有一个特殊情况,就是最大值和最小值都是一个元素。这种情况不能纳入到上面的计算过程中(2^(j-i) - 1 = 0),所以需要单独处理。

def numSubseq(self, nums: List[int], target: int) -> int:
    def pow(x, mod):
        ans = 1
        base = 2
        while x:
            if x % 2 == 1:
                ans = (ans * base) % mod
            base = (base * base) % mod
            x = x >> 1
        return ans

    MOD = 10 ** 9 + 7

    nums.sort()
    i, j = 0, len(nums) - 1
    ans = 0
    while i < j:
        if nums[i] + nums[j] > target:
            j -= 1
            continue
        d = pow(j-i ,MOD)
        ans = (ans + d - 1 + MOD) % MOD
        i += 1

    for x in nums:
        if 2 * x <= target:
            ans = (ans + 1) % MOD
        else:
            break

    return ans