(LeetCode 每日一题) 1498. 满足条件的子序列数目 (双指针)

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

思路：排序+双指针，时间复杂度0(nlogn)。

C++版本：

class Solution {
public:
    const int mod=1e9+7;
    int numSubseq(vector<int>& nums, int target) {
        int n=nums.size();
        // 获得 2^1....2^n
        vector<int> p(n+1);
        p[0]=1;
        for(int i=1;i<=n;i++){
            p[i]=(long long)p[i-1]*2%mod;
        }
        // 升序排序
        sort(nums.begin(),nums.end());
        // 双指针
        int left=0,right=n-1;
        // 答案
        long long sum=0;
        // 开始遍历
        while(left<=right){
        	// 说明[left,right]区间的子序列都符合要求
            if(nums[left]+nums[right]<=target){
            	// [left+1,right]区间里的元素可选可不选
                sum=(sum+p[right-left])%mod;
                // 下一个最小数
                left++;
            }else{
            	// 不符合要求，最大值太大了
                right--;
            }
        }
        return sum;
    }
};

JAVA版本：

class Solution {
    static final int mod=1000000007;
    public int numSubseq(int[] nums, int target) {
        int n=nums.length;
        int[] p=new int[n+1];
        p[0]=1;
        for(int i=1;i<=n;i++){
            p[i]=(int)((long)p[i-1]*2%mod);
        }
        Arrays.sort(nums);
        int left=0,right=n-1;
        long  sum=0;
        while(left<=right){
            if(nums[left]+nums[right]<=target){
                sum=(sum+p[right-left])%mod;
                left++;
            }else{
                right--;
            }
        }
        return (int)sum;
    }
}

Go版本：

const mod=1000000007

func numSubseq(nums []int, target int) int {
    n:=len(nums)
    p:=make([]int,n+1)
    p[0]=1
    for i:=1;i<=n;i++ {
        p[i]=p[i-1]*2%mod
    }
    slices.Sort(nums)
    left,right,sum:=0,n-1,0
    for left<=right {
        if nums[left]+nums[right]<=target {
            sum=(sum+p[right-left])%mod
            left++
        }else {
            right--
        }
    }
    return sum
}