2389. 和有限的最长子序列 Easy
给你一个长度为 n 的整数数组 nums ，和一个长度为 m 的整数数组 queries 。
返回一个长度为 m 的数组 answer ，其中 answer[i] 是 nums 中 元素之和小于等于 queries[i] 的 子序列 的 最大 长度 。
子序列 是由一个数组删除某些元素（也可以不删除）但不改变剩余元素顺序得到的一个数组。
示例 1:
输入：nums = [4,5,2,1], queries = [3,10,21]
输出：[2,3,4]
解释：queries 对应的 answer 如下：
子序列 [2,1] 的和小于或等于 3 。可以证明满足题目要求的子序列的最大长度是 2 ，所以 answer[0] = 2 。
子序列 [4,5,1] 的和小于或等于 10 。可以证明满足题目要求的子序列的最大长度是 3 ，所以 answer[1] = 3 。
子序列 [4,5,2,1] 的和小于或等于 21 。可以证明满足题目要求的子序列的最大长度是 4 ，所以 answer[2] = 4 。
示例 2:
输入：nums = [2,3,4,5], queries = [1]
输出：[0]
解释：空子序列是唯一一个满足元素和小于或等于 1 的子序列，所以 answer[0] = 0 。
解题思路
输入： 给你两个正整数数组 nums 和 queries
输出： 返回 nums 中小于等于每个 queries 的元素的最长子数组
本题属于二分查找 + 前缀和问题。
我们可以先对 nums 排好序，再对其求前缀和数组 prefix_sum
之后就可以将问题转化成在这个前缀和数组中，找到第一个大于 queries 中的元素的下标
最后将这些下标组合起来就是答案
代码实现
python
class Solution:
def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
nums.sort() # 先排序
prefix = [0] * len(nums)
prefix[0] = nums[0]
# 构造前缀和数组
for i in range(1, len(nums)):
prefix[i] = prefix[i - 1] + nums[i]
# 二分查找：找出 prefix 中 <= target 的最大索引 + 1 就是答案
def lower_bound(target):
left, right = 0, len(prefix) - 1
res = -1
while left <= right:
mid = (left + right) // 2
if prefix[mid] <= target:
res = mid # 记录当前可行长度
left = mid + 1
else:
right = mid - 1
return res + 1 # 转换为子序列长度
return [lower_bound(q) for q in queries]javascript
/**
* @param {number[]} nums
* @param {number[]} queries
* @return {number[]}
*/
var answerQueries = function(nums, queries) {
function lowerBound(nums, target) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
nums.sort((a, b) => a - b);
const ans = [];
const prefixSum = [nums[0]];
for (let i = 1; i < nums.length; i ++) {
prefixSum[i] = prefixSum[i - 1] + nums[i];
}
for (let x of queries) {
ans.push(lowerBound(prefixSum, x + 1));
}
return ans;
};复杂度分析
时间复杂度：O(log n)
空间复杂度：O(1)