2389.和有限的最长子序列

链接：2389.和有限的最长子序列
难度：Easy
标签：贪心、数组、二分查找、前缀和、排序
简介：返回一个长度为 m 的数组 answer ，其中 answer[i] 是 nums 中 元素之和小于等于 queries[i] 的 子序列 的 最大 长度  。

题解 1 - python

• 编辑时间：2023-03-17
• 执行用时：48ms
• 内存消耗：15.1MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
        n, m = len(nums), len(queries)
        idxs = [i for i in range(m)]
        idxs.sort(key=lambda v: queries[v])
        res = [0 for i in range(m)]
        nums.sort()
        idx, sums = 0, 0
        for i in range(m):
            while idx < n and sums + nums[idx] <= queries[idxs[i]]:
                sums += nums[idx]
                idx += 1
            res[idxs[i]] = idx
        return res

题解 2 - typescript

• 编辑时间：2022-08-28
• 执行用时：72ms
• 内存消耗：44.4MB
• 编程语言：typescript
• 解法介绍：排序后遍历。

function answerQueries(nums: number[], queries: number[]): number[] {
        nums.sort((a, b) => a - b);
        return queries.map(num => {
          let i = 0;
          let cur = 0;
          while (i < nums.length && cur + nums[i] <= num) cur += nums[i++];
          return i;
        });
      }

题解 3 - rust

• 编辑时间：2023-03-17
• 执行用时：4ms
• 内存消耗：2.1MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn answer_queries(mut nums: Vec<i32>, queries: Vec<i32>) -> Vec<i32> {
        nums.sort();
        let (n, m) = (nums.len(), queries.len());
        let mut idxs = (0..m).collect::<Vec<usize>>();
        idxs.sort_by(|v1, v2| queries[*v1].cmp(&queries[*v2]));
        let mut res = (0..m).map(|v| v as i32).collect::<Vec<i32>>();
        let (mut idx, mut sum) = (0, 0);
        for i in 0..m {
            while idx < n && sum + nums[idx] <= queries[idxs[i]] {
                sum += nums[idx];
                idx += 1;
            }
            res[idxs[i]] = idx as i32;
        }
        res
    }
}

题解 4 - cpp

• 编辑时间：2023-03-17
• 执行用时：20ms
• 内存消耗：13.3MB
• 编程语言：cpp
• 解法介绍：排序后遍历。

class Solution {
public:
    vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {
        int n = nums.size(), m = queries.size();
        vector<int> idxs(m), res(m, 0);
        for (int i = 0; i < m; i++) idxs[i] = i;
        sort(idxs.begin(), idxs.end(), [&](auto &a, auto &b){
            return queries[a] < queries[b];
        });
        sort(nums.begin(), nums.end());
        int idx = 0, sum = 0;
        for (int i = 0; i < m; i++) {
            while (idx < n && sum + nums[idx] <= queries[idxs[i]]) sum += nums[idx++];
            res[idxs[i]] = idx;
        }
        return res;
    }
};