1498. 满足条件的子序列数目 [medium]

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

给你一个整数数组 nums 和一个整数 target 。

请你统计并返回 nums 中能满足其最小元素与最大元素的和小于或等于 target 的非空子序列的数目。

由于答案可能很大，请将结果对 10^9 + 7 取余后返回。

示例 1：

输入：nums = [3,5,6,7], target = 9
输出：4
解释：有 4 个子序列满足该条件。
[3] -> 最小元素 + 最大元素 <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)

示例 2：

输入：nums = [3,3,6,8], target = 10
输出：6
解释：有 6 个子序列满足该条件。（nums 中可以有重复数字）
[3] , [3] , [3,3], [3,6] , [3,6] , [3,3,6]

示例 3：

输入：nums = [2,3,3,4,6,7], target = 12
输出：61
解释：共有 63 个非空子序列，其中 2 个不满足条件（[6,7], [7]）
有效序列总数为（63 - 2 = 61）

示例 4：

输入：nums = [5,2,4,1,7,6,8], target = 16
输出：127
解释：所有非空子序列都满足条件 (2^7 - 1) = 127

提示：

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^6
1 <= target <= 10^6

通过次数1,775 | 提交次数5,780

First Try

感觉挺简洁的了，应该也就O(N)的复杂度，不知道为什么时间这么慢。。。

唯一耗时的看来也就sorted语句了，O(NlgN)复杂度...

class Solution(object):
    def numSubseq(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        nums = sorted(nums)   # 排序后才好处理
        start, end = 0, len(nums) - 1
        rv = 0
        rem = 10 ** 9 + 7
        while start <= end:  # 允许start和end相等
            if nums[start] + nums[end] <= target:
                # print(start, end, end - start + 1, rv)
                # 每次只固定考察有左边界在的子序列，其他子序列自有后来的元素去收
                # 其次自身也需要加一波，毕竟nums[start]肯定小于nums[end], nums[start] + nums[start] < target
                
                # 这个写法就有问题，正常应该是start固定了，后面的元素选取所有可能即可
                # rv += end - start + 1
                # 如果end - start为0，则刚好为一个元素左边界，两倍依然小于等于target, 符合要求
                # 这个写法竟然也超出时间限制了，实时处理rem竟然拖延了时间
                # rv = (rv + 2 ** (end - start)) % rem 
                rv += 2 ** (end - start)
                start += 1 # 下一波走起
                # break
            else:
                end -= 1
                
        return rv % rem

执行用时：9900 ms, 在所有 Python 提交中击败了5.66%的用户
内存消耗：20.3 MB, 在所有 Python 提交中击败了100.00%的用户

speed up version

没想到提前对2的n次方进行缓存，竟然还能加快速度到这种地步。。

不知道原生态的n次方复杂度是多少，加速版一般使用快速幂,每个元素使用递归的复杂度是O(lgN)，或者下面这种提前把每个都计算出来，复杂度平摊下来反而是O(1)。

class Solution(object):
    def numSubseq(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        # 竟然还需要对幂进行提前计算...
        powerc = [1]
        for i in range(1, len(nums)):
            powerc.append(2 * powerc[-1])

        nums = sorted(nums)   # 排序后才好处理
        start, end = 0, len(nums) - 1
        rv = 0
        rem = 10 ** 9 + 7
        while start <= end:  # 允许start和end相等
            if nums[start] + nums[end] <= target:
                # print(start, end, end - start + 1, rv)
                # 每次只固定考察有左边界在的子序列，其他子序列自有后来的元素去收
                # 其次自身也需要加一波，毕竟nums[start]肯定小于nums[end], nums[start] + nums[start] < target
                
                # 这个写法就有问题，正常应该是start固定了，后面的元素选取所有可能即可
                # rv += end - start + 1
                # 如果end - start为0，则刚好为一个元素左边界，两倍依然小于等于target, 符合要求
                # 这个写法竟然也超出时间限制了，实时处理rem竟然拖延了时间
                # rv = (rv + 2 ** (end - start)) % rem 

                # 竟然影响了速度？
                # rv += 2 ** (end - start)
                rv += powerc[end - start]
                start += 1 # 下一波走起
                # break
            else:
                end -= 1
                
        return rv % rem

执行用时：1048 ms, 在所有 Python 提交中击败了62.26%的用户
内存消耗：599.5 MB, 在所有 Python 提交中击败了100.00%的用户

1498. 满足条件的子序列数目 [medium]​

First Try​

1498. 满足条件的子序列数目 [medium]

First Try