一、题目

给你一个长度为 n 的整数数组 nums ，和一个长度为 m 的整数数组 queries 。

返回一个长度为 m 的数组 answer ，其中 answer[i] 是 nums 中 元素之和小于等于 queries[i] 的 子序列 的 最大 长度 。

子序列 是由一个数组删除某些元素（也可以不删除）但不改变剩余元素顺序得到的一个数组。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-subsequence-with-limited-sum/description/

二、C++解法

我的思路及代码

由于是返回的子序列的大小，所以我们可以对原数组进行排序，然后采用遍历的方式，挨个将 nums 前面的 j 位相加，当前和大于 queries[i] 时，我们保存此时的 j 即可。值得注意的是，如果所有的 nums 相加都小于当前的 queries[i] 时，我们需要单独给 ans 的最后一个数设置为 nums 的长度。

class Solution {
public:vector answerQueries(vector& nums, vector& queries) {int size = queries.size();vector ans(size);sort(nums.begin(),nums.end());for(int i=0;iint temp = 0;int j;for(j=0;jtemp+=nums[j];if(temp>queries[i]){ans[i] = j;break;}}if(j==nums.size()){  ans[i] = j;}}return ans;}
};

• 时间复杂度：O((n × m+nlog⁡n)，其中 n 是数组 nums 的长度，m 是数组 queries 的长度。对 nums 进行排序需要 O(nlog⁡n)的时间，遍历需要 n × m 的时间
• 空间复杂度：O(1)。返回值不计入空间复杂度

官方参考代码

排序+前缀和+二分查找

先对 nums 进行排序后进行前缀和处理，然后通过二分查找定位到当前的 queries [i] 是在前缀和数组中的哪一个位置，当前位置也就是答案

class Solution {
public:vector answerQueries(vector& nums, vector& queries) {int n = nums.size(), m = queries.size();sort(nums.begin(), nums.end());vector f(n + 1);for (int i = 0; i < n; i++) {f[i + 1] = f[i] + nums[i];}vector answer(m);for (int i = 0; i < m; i++) {answer[i] = upper_bound(f.begin(), f.end(), queries[i]) - f.begin() - 1;}return answer;}
};

• 时间复杂度：O((n+m)×log⁡n)，其中 n 是数组 nums 的长度，m 是数组 queries 的长度。对 nums 进行排序需要 O(nlog⁡n)的时间，二分查找需要 O(log⁡n) 的时间
• 空间复杂度：O(n)。返回值不计入空间复杂度