wp网站模板,无极app下载最新版,怎样做才能让百度搜到网站产品,做网站如何购买服务器1. 题目
给你一个整数数组 nums 和一个整数 target 。
请你统计并返回 nums 中能满足其最小元素与最大元素的 和 小于或等于 target 的 非空 子序列的数目。
由于答案可能很大#xff0c;请将结果对 10^9 7 取余后返回。
示例 1#xff1a;
输入#xff1a;nums [3,5,…1. 题目
给你一个整数数组 nums 和一个整数 target 。
请你统计并返回 nums 中能满足其最小元素与最大元素的 和 小于或等于 target 的 非空 子序列的数目。
由于答案可能很大请将结果对 10^9 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示例 4
输入nums [5,2,4,1,7,6,8], target 16
输出127
解释所有非空子序列都满足条件 (2^7 - 1) 127提示
1 nums.length 10^5
1 nums[i] 10^6
1 target 10^6来源力扣LeetCode 链接https://leetcode-cn.com/problems/number-of-subsequences-that-satisfy-the-given-sum-condition 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
排序遍历左端点 i 二分查找小于等于 target-nums[i]的最后一个数 j包含左端点 i 的满足条件的子序列个数为2j−i2^{j-i}2j−i 个然后 j−ij-ij−i 很大时用快速幂求取过程中取模避免溢出
class Solution { //Cint mod 1e97;
public:int numSubseq(vectorint nums, int target) {sort(nums.begin(),nums.end());int i 0, j;unsigned long long count 0;for(i 0; i nums.size(); i){if(nums[i] target/21)break;j bs(nums,target-nums[i]);if(j ! -1 j i)count (countmypow(j-i))%mod;}return count;}int bs(vectorint a, int t){int i 0, j a.size()-1, mid;while(i j){mid (ij)/2;if(a[mid] t)j mid-1;else{if(mida.size()-1 || a[mid1] t)return mid;elsei mid1;}}return -1;}int mypow(int n){long long s 1, p 2;while(n){if(n1)s * p, s % mod;p * p;p % mod;n / 2;}return s;}
};452 ms 48 MB
python3 解答
class Solution:# py3def numSubseq(self, nums: List[int], target: int) - int:mod int(1e97)nums.sort()def bs(t):i,j 0, len(nums)-1while i j:mid (ij)1if nums[mid] t:j mid-1else:if midlen(nums)-1 or nums[mid1] t:return midelse:i mid1return -1def mypow(n):s, p 1, 2while n:if n1:s * ps % modp * pp % modn // 2return scount 0for i in range(len(nums)):if nums[i] target//21:break;j bs(target-nums[i])if j ! -1 and j i:count (count mypow(j-i))%modreturn count1528 ms 23.7 MB
