| 题目链接 | 2389. 和有限的最长子序列 |
|---|---|
| 思路 | 贪心+排序+二分 |
| 题解链接 | 非暴力做法：前缀和 + 二分查找 + 原地 O(1) 空间（Python/Java/C++/Go） |
| 关键点 | 1. 贪心：由于元素和有上限，为了能让子序列尽量长，子序列中的元素值越小越好。 2. 本题要求计算元素和，因此元素在数组中的位置无关紧要，所以可以排序了。3. 把 nums 从小到大排序后，再从小到大选择尽量多的元素（相当于选择一个前缀），使这些元素的和不超过询问值。 |
| 时间复杂度 | \(O((n+m)\log n)\) |
| 空间复杂度 | \(O(1)\) |
代码实现：
class Solution:
def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
nums.sort()
n = len(nums)
for i in range(1, n):
nums[i] += nums[i-1]
def upper_bound(val):
left, right = -1, n
while left + 1 < right:
mid = (left+right) // 2
if nums[mid] > val:
right = mid
else:
left = mid
return right
for i, q in enumerate(queries):
queries[i] = upper_bound(q)
return queries
Python-官方库
class Solution:
def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
nums.sort()
for i in range(1, len(nums)):
nums[i] += nums[i-1]
for i, q in enumerate(queries):
queries[i] = bisect_right(nums, q)
return queries