题目链接:2389. 和有限的最长子序列
方法:前缀和 + 二分查找
解题思路
- 根据题意,子序列与\(nums\)数组的元素顺序无关,因此可以先对\(nums\)从小到大排序,并计算前缀和\(nums[i] += nums[i - 1]\),此时的\(nums[i]\)表示原来nums数组\([0, i]\)的区间和。
- 那么\(answer[i] = idx + 1\),其中\(idx\)为满足\(nums[idx] <= queries[i]\)的\(nums\)中的最靠后坐标。则此时就变为在\(nums\)数组中找第一个大于\(queries[i]\)的下标。
代码
class Solution {
public:
vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {
int m = queries.size();
vector<int> ans(m);
sort(nums.begin(), nums.end());
for (int i = 1; i < nums.size(); i ++ ) nums[i] += nums[i - 1];
for (int i = 0; i < m; i ++ ) ans[i] = upper_bound(nums.begin(), nums.end(), queries[i]) - nums.begin();
return ans;
}
};
复杂度分析
时间复杂度:\(O((n + m)logn),n = nums.size(), m = queries.size()\);
空间复杂度:\(O(1)\)。