题目：满足条件的子序列数目

1. 题目描述

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

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

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

2. 示例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)

3. 题解：预先存储+双指针

预先排序。创建辅助数组，预先统计子序列的数目且取余。采用双指针分别指向数组两端l,r，如果两端和大于target则直接跳过r--,否则累加子数列数目。代码如下：

class Solution {
    public int numSubseq(int[] nums, int target) {
        Arrays.sort(nums);
        int[] temp = new int[nums.length];
        int mode = 1000000007;
        temp[0] = 1;
        for(int i = 1; i < temp.length; ++i){
            temp[i] = (temp[i - 1] << 1) % mode;
        }
        int res = 0;
        int l = 0; 
        int r = nums.length - 1;
        while(l <= r){
            if(nums[l] + nums[r] > target){
                --r;
            }else{
                res = (res + temp[r -l]) % mode;
                ++l;
            }
        }
        return res;

    }
}