贪心

想要子序列的长度最长，就要子序列的和最小，显然从小到大选取数组数字最合适。本题的子序列是可间断的数组元素（子序列不一定连续），数组元素的顺序不影响子序列的和。对数组 nums 排序，就很方便从小到大选数了。

class Solution {
public:vector answerQueries(vector& nums, vector& queries) {int n = nums.size();int m = queries.size();sort(nums.begin(), nums.end());int sum = 0;vector ans(m);for (int i = 0, j = 0; i < m; i ++) {while (j < n && sum <= queries[i]) sum += nums[j ++];while (sum > queries[i]) sum -= nums[-- j];ans[i] = j;}return ans;}
};

1. 时间复杂度 : O(nlogn+n×m)O(nlogn + n\times m)O(nlogn+n×m) ， nnn 是数组 numsnumsnums 的大小，mmm 是数组 queriesqueriesqueries 的大小，排序 numsnumsnums 的时间复杂度是 O(nlogn)O(nlogn)O(nlogn) ，枚举查询和数字的时间复杂度 O(n×mO(n \times mO(n×m)，总体时间复杂度O(nlogn+n×m)O(nlogn + n\times m)O(nlogn+n×m) 。
2. 空间复杂度 : O(logn)O(logn)O(logn) ， 不考虑答案使用的空间，快排的空间复杂度 O(logn)O(logn)O(logn) 。

前缀和 + 二分查找

枚举 numsnumsnums 数组，其实是按顺序增减数字，也就是看某个数组下标的前缀和，和查询做比较。直接构造前缀和数组，二分查找前缀和数组，以加速枚举数组 numsnumsnums 的效率。

class Solution {
public:vector answerQueries(vector& nums, vector& queries) {int n = nums.size();int m = queries.size();sort(nums.begin(), nums.end());int sum = 0;vector p(n + 1);for (int i = 1; i <= n; i ++) p[i] = p[i - 1] + nums[i - 1];vector ans(m);for (int i = 0, j = 0; i < m; i ++) {int l = 0, r = n - 1;while(l <= r) {int mid = l + (r - l >> 1);if (p[mid + 1] > queries[i]) r = mid - 1;else l = mid + 1;}ans[i] = l;}return ans;}
};

1. 时间复杂度 : O(n×(logn+logm))O(n \times (logn + logm))O(n×(logn+logm)) ， nnn 是数组 numsnumsnums 的大小，mmm 是数组 queriesqueriesqueries 的大小，排序 numsnumsnums 的时间复杂度是 O(nlogn)O(nlogn)O(nlogn) ，枚举查询和二分查找的时间复杂度 O(nlogmO(nlogmO(nlogm)，总体时间复杂度O(n×(logn+logm))O(n \times(logn + logm))O(n×(logn+logm)) 。
2. 空间复杂度 : O(n)O(n)O(n) ， 不考虑答案使用的空间，前缀和数组的空间复杂度 O(n)O(n)O(n) 。

AC

时空对比。

致语

• 理解思路很重要
• 读者有问题请留言，清墨看到就会回复的。