2389.Longest Subsequence With Limited Sum === ###### tags: `Easy`,`Array`,`Binary Search`,`Greedy`,`Sorting`,`Prefix Sum` [2389. Longest Subsequence With Limited Sum](https://leetcode.com/problems/longest-subsequence-with-limited-sum/) ### 題目描述 You are given an integer array nums of length n, and an integer array queries of length m. Return an array `answer` of length `m` where `answer[i]` is the **maximum** size of a **subsequence** that you can take from `nums` such that the **sum** of its elements is less than or equal to `queries[i]`. A **subsequence** is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements. ### 範例 **Example 1:** ``` Input: nums = [4,5,2,1], queries = [3,10,21] Output: [2,3,4] Explanation: We answer the queries as follows: - The subsequence [2,1] has a sum less than or equal to 3. It can be proven that 2 is the maximum size of such a subsequence, so answer[0] = 2. - The subsequence [4,5,1] has a sum less than or equal to 10. It can be proven that 3 is the maximum size of such a subsequence, so answer[1] = 3. - The subsequence [4,5,2,1] has a sum less than or equal to 21. It can be proven that 4 is the maximum size of such a subsequence, so answer[2] = 4. ``` **Example 2:** ``` Input: nums = [2,3,4,5], queries = [1] Output: [0] Explanation: The empty subsequence is the only subsequence that has a sum less than or equal to 1, so answer[0] = 0. ``` **Constraints**: * `n == nums.length` * `m == queries.length` * `1 <= n, m <= 1000` * 1 <= `nums[i]`, `queries[i]` <= 10^6^ ### 解答 #### Python ```python= class Solution: def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]: return [bisect_right(list(accumulate(sorted(nums))), query) for query in queries] ``` > [name=Kobe][time=Mon, Dec 26, 2022] ### Reference [回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)