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

Problem: 1498. 满足条件的子序列数目首先排序的然后计算出2的幂次取模以后的值放在powered数组中删掉target的数字遍历nums数组当前索引是i固定选择索引i处的数字nums[i]此时只需要找到大于(target-nums[i])的最小数字的索引ind从i1开始二分查找查看nums[ind-1]的数字若nums[ind-1] a则满足条件的数字在索引范围内[i, ind-1]像target9nums[3, 8], i0, 此时ind 1所以sum sum powered[ind-1]对nums[ind-1] a索引范围内的数字 [i, ind-1]每个数字都是两种可能要么选择要么不选择也就是2的幂已经固定选择了nums[i]所以不存在重复的可能累加取模即可的Codeclass Solution { public: const int mod 1e9 30 - 23; int numSubseq(vectorint nums, int target) { sort(nums.begin(), nums.end()); while(nums.back() target) nums.pop_back(); int n nums.size(), a, ind; long long sum 0, tmp 1; vectorlong long powered{1}; for(int i 1; i n; i) { tmp (tmp 1) % mod; powered.push_back(tmp); } for(int i 0; i n; i) { a target - nums[i]; ind upper_bound(nums.begin() i 1, nums.end(), a) - nums.begin(); ind--; if(nums[ind] a) sum (sum powered[ind - i]) % mod; } return sum; } };