[双指针]1498. 满足条件的子序列数目

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

给你一个整数数组 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

方法：排序+相向双指针

⚠注意：子序列的最小值和最大值可以是同一个数，此时子序列长度为 1。

解题思路：

1、初始化 left=0，right=n−1，分别表示剩余元素中的最小下标和最大下标。
2、如果 nums[left]+nums[right]>target，这意味着 nums[right] 太大了，所以 nums[right] 不可能作为剩余元素中的子序列最大值。去掉 nums[right]（也就是把 right 减一）。求解[left,right-1]
3、如果 nums[left]+nums[right]≤target，这意味着 nums[left] 可以作为子序列的最小值，不仅与 nums[right] 相加满足要求，与更小的 nums[right−1],nums[right−2],…,nums[left] 相加，也满足要求。换句话说，如果选 nums[left] 作为最小值，那么其余下标在 [left+1,right] 中的这 right−left 个数可选可不选，有 2 **（right-left）种方案。

4、接下来，去掉 nums[left]（也就是把 left 加一），求解 [left+1,right] 中满足要求的子序列数目。
循环直到没有剩余元素，即 left>right。

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

优化：

# 将MOD和MX定义为常量，提高了代码的可读性和可维护性。
MOD = 1_000_000_007
MX = 100_000
# 预先计算了pow2数组，存储了2的幂次模MOD的结果，避免了重复计算
pow2 = [1]*MX
for i in range(1,MX):pow2[i] = pow2[i-1]*2%MODclass Solution:def numSubseq(self, nums: List[int], target: int) -> int:n = len(nums)left = 0right = n-1nums.sort()ans = 0while left <= right:if nums[left]+nums[right] <= target:ans += pow2[right - left]left += 1else:right -= 1return ans%MOD

关键点分析

1. ​预处理 pow2 数组的含义​：

   • pow2[i] 存储的是 2^i % MOD 的值，即 2 的 i 次方对 MOD 取模的结果。
   • 由于 MOD = 1_000_000_007 是一个大质数，且 2 和 MOD 互质，因此 pow2[i] 的计算是正确的。

2. ​为什么可以提前计算 pow2？​​

   • 在题目中，我们需要计算 2^{k} % MOD（其中 k = right - left），而 k 的最大可能值是 n-1（即 MX-1）。
   • 由于 MX = 100_000，我们提前计算 pow2[0..MX-1] 可以保证所有可能的 k 都能直接查表，避免重复计算。

3. ​是否会影响最终结果的正确性？​​

   • ​不会，因为：
     • 在计算 ans += pow2[right - left] 时，pow2[right - left] 已经是 2^{right-left} % MOD 的值。
     • 最终 ans 可能会超过 MOD，所以最后再取一次模 ans % MOD 确保结果正确。
     • 由于 (a % MOD + b % MOD) % MOD = (a + b) % MOD，所以提前对 pow2 取模不会影响最终结果的正确性。

为什么直接计算 2^{k}可能有问题？​​

• 如果 k 很大（比如 k = 1e5），直接计算 2^k 会导致数值非常大，可能会超出 Python 的整数范围（虽然 Python 支持大整数，但计算效率会降低）。
• 更严重的是，如果 k 很大，2^k 会是一个天文数字，计算 2^k % MOD 时，虽然 Python 不会溢出，但计算时间会变长（相比查表 pow2[k] 直接取用）。

​结论​

• ​预处理 pow2 是正确的，不会影响最终结果的正确性，反而能提高计算效率。
• 第二个代码（直接计算 2^{k}）虽然功能正确，但在大数据情况下效率较低，而第一个代码通过预处理优化了计算过程。

​改进建议​

如果题目给定的 nums 的长度 n 可能超过 MX = 100_000，那么应该调整 MX 的大小，比如：

MX = 10**5 + 10  # 稍微比题目给定的最大值大一点

以确保 pow2 数组足够覆盖所有可能的 k = right - left。