满足条件的子序列数目

标签: 数组 双指针 二分查找 排序

难度: Medium

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

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

由于答案可能很大，请将结果对 109 + 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）

提示：

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 106
  • 1 <= target <= 106

Submission

运行时间: 210 ms

内存: 25.8 MB

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        mod = 10 ** 9 + 7
        nums.sort()
        count = 0
        left, right = 0, len(nums) - 1
        while left <= right:
            if nums[left] + nums[right] > target:
                right -= 1
            else:
                count += pow(2, right - left, mod)
                left += 1
        
        return count % mod

Explain

首先，将数组 nums 排序。这样做的目的是为了能快速找到任意子序列的最小和最大元素。定义两个指针 left 和 right，分别代表当前考虑的子序列的最小元素和最大元素的位置。初始化 left 为 0，right 为 nums 长度减一。在遍历数组时，如果 nums[left] + nums[right] 小于等于 target，意味着从 left 到 right 之间的所有子序列都满足条件，因为 nums[left] 是可能的最小值，而 nums[right] 是可能的最大值。每次这样的情况出现时，可以用 pow(2, right - left, mod) 来计算当前 left 和 right 之间的所有子序列的数量（即 2 的 (right-left) 次幂），因为每个元素可以选择包含或不包含。如果 nums[left] + nums[right] 大于 target，由于数组是排序的，需要将 right 指针左移，以尝试减小最大元素的值。循环直到 left 超过 right。最后，返回 count 对 mod 的余数作为结果。

时间复杂度: O(n log n)

空间复杂度: O(n)

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        mod = 10 ** 9 + 7  # 定义模数
        nums.sort()  # 对数组进行排序
        count = 0  # 初始化符合条件的子序列计数器
        left, right = 0, len(nums) - 1  # 初始化左右指针
        while left <= right:  # 当左指针不超过右指针时进行循环
            if nums[left] + nums[right] > target:  # 如果当前最小和最大元素之和大于目标值
                right -= 1  # 移动右指针以减小最大元素的值
            else:  # 如果当前最小和最大元素之和小于等于目标值
                count += pow(2, right - left, mod)  # 将从 left 到 right 的所有子序列计入计数器
                left += 1  # 移动左指针以增大最小元素的值
        return count % mod  # 返回计数器的值对模数取余的结果

Explore

在算法中进行排序是为了确保数组元素是按递增顺序排列的。这样做的主要目的是为了简化最小和最大元素的选择过程。当数组被排序后，可以很容易地通过左右指针来分别追踪当前子序列中可能的最小值和最大值。这种方式使得算法在判断子序列是否满足条件（即子序列中最小元素与最大元素之和是否小于等于目标值）时更为直接和高效。如果不排序，就需要对每一个可能的子序列计算最小值和最大值，这将大大增加算法的复杂度。

当数组已经排序并且nums[left]与nums[right]的和小于等于目标值时，基于排序数组的性质，可以确认任何包含nums[left]并且元素位于left和right之间的子序列都会满足条件。因为nums[right]是这个范围内最大的数，所以任何小于等于nums[right]的其他数与nums[left]的和也必定小于等于目标。因此，可以通过计算2的（right-left）次幂来得出从left至right的所有可能组合，其中每个元素都可以选择包含或不包含。

这个计算过程基于组合学中的原理，即每个元素在子序列中有包含或不包含两种选择。对于任意给定的元素组（此处为从left到right的元素），每个元素都可以独立选择是否出现在子序列中。因此，总的组合数为每个元素的两种选择的乘积，即2的（right-left）次幂。使用pow函数计算这个值可以高效地得到结果，并且通过mod参数保证结果不会因为数值过大而溢出。

当nums[left] + nums[right]大于目标值时，由于数组是排序的，说明nums[right]是太大，不能与nums[left]组成有效的子序列。移动右指针向左是为了尝试找到一个较小的最大值使组合有效。如果移动左指针向右，则会导致最小值增大，这会使得和更大，不利于满足条件。因此，适当的操作是减小最大值，即移动右指针。