题目
给你一个整数数组 nums 和一个整数 target 。
请你统计并返回 nums 中能满足其最小元素与最大元素的 和 小于或等于 target 的非空子序列的数目。
由于答案可能很大，请将结果对 10^9 + 7 取余后返回。
思路
排序 + 双指针
将数组从小到大排序, 双指针left指向排好序的第一个元素, right指向最后一个.
首先寻找符合条件的左右端点, 显然nums[left] + nums[right] <= target 时,符合条件, 此时我们统计可以使用的子序列个数为2r−l2^{r -l}, 注意每次都默认使用左指针指向的元素. 统计后移动左指针. 这样, 每一次循环子序列不会发生漏记的情况(子序列最小值都是没有使用过的最小值).
代码如下
class Solution:
def numSubseq(self, nums: List[int], target: int) -> int:
nums.sort()
if nums[0] * 2 > target:
return 0
MOD = 10 ** 9 + 7
left = 0
right = len(nums) - 1
ret = 0
while left <= right:
if nums[left] + nums[right] <= target:
ret += 2**(right-left)
ret %= MOD
left += 1
else:
right -= 1
return ret
本文地址：https://blog.csdn.net/Hoooo_233/article/details/107140413
![2022-07-29：一共有n个人，从左到右排列，依次编号0~n-1， h[i]是第i个人的身高， v[i]是第i个人的分数， 要求从左到右选出一个子序列，在这个子序列中的人，从左到右身高是不下降的。](https://www.kunjuke.com/file/css/thumb/10.jpg/280-180.jpg)
![2022-08-18:每一个序列都是[a,b]的形式，a ＜ b 序列连接的方式为，前一个序列的b，要等于后一个序列的a 比如 : [3, 7]、[7, 13]、[13, 26]这三个序列就可以依次连](https://www.kunjuke.com/file/css/thumb/7.jpg/280-180.jpg)
