class Solution {
public:
vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {
}
};
2389. 和有限的最长子序列
给你一个长度为 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 。
提示：
n == nums.lengthm == queries.length1 <= n, m <= 10001 <= nums[i], queries[i] <= 106原站题解
golang 解法, 执行用时: 20 ms, 内存消耗: 5.2 MB, 提交时间: 2022-08-31 10:25:37
func answerQueries(nums, queries []int) []int {
sort.Ints(nums)
for i := 1; i < len(nums); i++ {
nums[i] += nums[i-1] // 原地求前缀和
}
for i, q := range queries {
queries[i] = sort.SearchInts(nums, q+1) // 复用 queries 作为答案
}
return queries
}
python3 解法, 执行用时: 48 ms, 内存消耗: 15.1 MB, 提交时间: 2022-08-31 10:24:07
class Solution:
def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
nums.sort()
for i in range(1, len(nums)):
nums[i] += nums[i - 1] # 原地求前缀和
for i, q in enumerate(queries):
queries[i] = bisect_right(nums, q) # 复用 queries 作为答案
return queries