和有限的最长子序列

难度: Easy

给你一个长度为 n 的整数数组 nums ，和一个长度为 m 的整数数组 queries 。

返回一个长度为 m 的数组 answer ，其中 answer[i] 是 nums 中元素之和小于等于 queries[i] 的 子序列 的最大长度。

子序列 是由一个数组删除某些元素（也可以不删除）但不改变剩余元素顺序得到的一个数组。

示例 1：

输入：nums = [4,5,2,1], queries = [3,10,21]
输出：[2,3,4]
解释：queries 对应的 answer 如下：
- 子序列 [2,1] 的和小于或等于 3 。可以证明满足题目要求的子序列的最大长度是 2 ，所以 answer[0] = 2 。
- 子序列 [4,5,1] 的和小于或等于 10 。可以证明满足题目要求的子序列的最大长度是 3 ，所以 answer[1] = 3 。
- 子序列 [4,5,2,1] 的和小于或等于 21 。可以证明满足题目要求的子序列的最大长度是 4 ，所以 answer[2] = 4 。

示例 2：

输入：nums = [2,3,4,5], queries = [1]
输出：[0]
解释：空子序列是唯一一个满足元素和小于或等于 1 的子序列，所以 answer[0] = 0 。

提示：

n == nums.length
m == queries.length
1 <= n, m <= 1000
1 <= nums[i], queries[i] <= 10⁶

Submission

运行时间: 33 ms

内存: 16.5 MB

from typing import List
import bisect

class Solution:
    def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
        nums.sort()  # 对 nums 进行排序
        prefix_sums = [0]  # 初始化前缀和数组，第一个元素为 0，用于处理空子序列的情况
        for num in nums:
            prefix_sums.append(prefix_sums[-1] + num)  # 计算前缀和
        
        results = []  # 存储结果的列表
        for query in queries:
            # 使用 bisect_right 找到第一个大于 query 的前缀和的位置，该位置减一即为满足条件的子序列的最大长度
            idx = bisect.bisect_right(prefix_sums, query)
            results.append(idx - 1)  # 减一是因为前缀和数组中包含了一个额外的 0 元素
        
        return results

from typing import List
import bisect

class Solution:
    def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
        nums.sort()  # 对 nums 进行排序
        prefix_sums = [0] * (len(nums) + 1)  # 初始化前缀和数组，包括一个额外的 0 作为哨兵值（用于处理空子序列）
        for i in range(1, len(prefix_sums)):  # 计算前缀和（包含 nums 中的所有元素）
            prefix_sums[i] = prefix_sums[i - 1] + nums[i - 1]
        
        results = []  # 存储结果的列表
        for query in queries:
            # 使用 bisect_right 找到第一个大于 query 的前缀和的位置，然后减一得到最大子序列的结束索引
            idx = bisect.bisect_right(prefix_sums, query, key=lambda x: x if x <= query else float('inf')) - 1
            results.append(idx)  # 这个索引就是满足条件的子序列的最大长度（因为子序列可以从数组中的任何位置开始）
        
        return results

from typing import List
import bisect

class Solution:
    def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
        nums.sort()  # 对 nums 进行排序
        prefix_sums = [0] * (len(nums) + 1)  # 初始化前缀和数组，包括一个额外的 0 作为哨兵值（用于处理空子序列）
        for i in range(1, len(prefix_sums)):  # 计算前缀和（包含 nums 中的所有元素）
            prefix_sums[i] = prefix_sums[i - 1] + nums[i - 1]
        
        results = []  # 存储结果的列表
        for query in queries:
            # 使用 bisect_right 找到第一个大于 query 的前缀和的索引
            idx = bisect.bisect_right(prefix_sums, query) - 1
            results.append(idx)  # 这个索引就是满足条件的子序列的最大长度（因为子序列可以从数组中的任何位置开始）
        
        return results

Explain

该题解通过将数组 nums 排序和计算前缀和数组来解决问题。首先对 nums 进行排序，这样较小的数字会在前面，有助于形成和较小的子序列。然后，计算 nums 的前缀和数组，前缀和数组用于快速求得任意子序列的和。对于每个查询，使用二分查找（通过 bisect_right 函数）在前缀和数组中找到第一个大于查询值的元素索引，然后将这个索引减一得到满足条件的最大子序列长度。

时间复杂度: O(n log n + m log n)

空间复杂度: O(n)

from typing import List
import bisect

class Solution:
    def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
        nums.sort()  # 对 nums 进行排序，使子序列的和的计算更加方便
        prefix_sums = [0] * (len(nums) + 1)  # 初始化前缀和数组，包含额外的 0 作为哨兵值
        for i in range(1, len(prefix_sums)):  # 计算前缀和
            prefix_sums[i] = prefix_sums[i - 1] + nums[i - 1]
        results = []  # 存储最终结果的列表
        for query in queries:  # 对每个查询进行处理
            idx = bisect.bisect_right(prefix_sums, query) - 1  # 使用二分查找得到最大子序列长度
            results.append(idx)  # 将结果加入列表
        return results  # 返回结果列表

Explore

首选排序和前缀和数组的方法，是因为这种方法可以高效地解决多个查询。通过排序，可以确保在构建前缀和数组时，后续元素的和总是递增的，这使得可以使用二分查找快速定位不超过查询值的最长子序列。如果直接遍历数组来求每个查询的结果，对于每个查询都需要从头到尾计算和并检查长度，这在面对大量数据和多个查询时效率较低。

排序后的 nums 数组保证了任何子序列的和都是递增的。构建的前缀和数组则允许我们快速计算任意前缀的和。在处理查询时，通过二分查找在前缀和数组中寻找最接近且不超过查询值的前缀和位置，从而快速确定最长的有效子序列长度。这种结合使用减少了重复的计算并提高了查询效率。

二分查找在前缀和数组中的目标是找到第一个大于查询值的元素的位置。使用 `bisect_right` 是因为我们需要确定所有小于或等于查询值的前缀和的最大范围，`bisect_right` 返回的是超过目标值的第一个元素的位置。如果使用 `bisect_left`，则得到的是不大于目标值的最小元素的位置，这无法直接应用于求解最长子序列长度的场景。

前缀和数组中添加的额外的0作为哨兵值，主要是为了处理空子序列的和以及简化边界条件的处理。这个0确保了前缀和数组在进行二分查找时，即使所有元素的和都大于查询值，也能返回正确的索引0，表示没有任何元素的和小于或等于查询值。此外，它也使得前缀和的计算从索引1开始变得更自然，不需要对数组下标做特殊处理。