2389. 和有限的最长子序列-526互联

方法：前缀和 + 二分查找

解题思路

根据题意，子序列与\(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)\)。