1498. Number of Subsequences That Satisfy the Given Sum Condition 区间最大最小

题目

https://leetcode.com/problems/number-of-subsequences-that-satisfy-the-given-sum-condition/submissions/
Given an array of integers nums and an integer target.

Return the number of non-empty subsequences of nums such that the sum of the minimum and maximum element on it is less or equal than target.

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: nums = [3,5,6,7], target = 9
Output: 4
Explanation: There are 4 subsequences that satisfy the condition.
[3] -> Min value + max value <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)
Example 2:

Input: nums = [3,3,6,8], target = 10
Output: 6
Explanation: There are 6 subsequences that satisfy the condition. (nums can have repeated numbers).
[3] , [3] , [3,3], [3,6] , [3,6] , [3,3,6]
Example 3:

Input: nums = [2,3,3,4,6,7], target = 12
Output: 61
Explanation: There are 63 non-empty subsequences, two of them don’t satisfy the condition ([6,7], [7]).
Number of valid subsequences (63 – 2 = 61).
Example 4:

Input: nums = [5,2,4,1,7,6,8], target = 16
Output: 127
Explanation: All non-empty subset satisfy the condition (2^7 – 1) = 127

Constraints:

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^6
1 <= target <= 10^6

思路

首先对数组进行排序
遍历以各元素开始的子序列,针对起始元素例如3,target为9时要求max最大为6,则找到最后一个小于等于6的位置,计算该长度内以3开头的子序列数量。
我们知道大小为3的数组的子集为 2^3-1,其中以第一个元素开头的子序列数量为 2^2,原理为第一位确定后,第二位可以要可以不要2种选择,第三位同理
注意 不要写r+=a%b,写 r = (r+a)%b

源码

class Solution {
public:
    long long res = 0;
    int pows[100005]={0};
    int numSubseq(vector<int>& nums, int k) {
        vector<int> re;
        sort(nums.begin(),nums.end());
        re = nums;
        reverse(re.begin(),re.end());

        pow2();
        for(int i = 0;i < nums.size();++i){
            if(nums[i] > k)break;
            int bd = k - nums[i];
            auto idx = lower_bound(re.begin(),re.end()-i,bd,greater<int>());   
            int len = (re.end()-idx)-i;
            cout <<len<<endl;
            if(len!=0)
            res = (res+pows[len-1])%(int)(1e9+7);
           // cout<<res<<endl;
        }
        return res;
    }
    void pow2(){
        pows[0]=1;
        for(int i = 1;i <= 1e5;++i){
            pows[i] = (2*pows[i-1])%(int)(1e9+7);
           // cout <<pows[i]<<endl;
        }
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注