How do I apply binary search in the Longest Subsequence With Limited Sum problem?

Binary search is used to find the maximum subsequence size whose sum is less than or equal to each query value. You search for the largest sum in the sorted prefix sum array that satisfies the query condition.

What is the time complexity of solving the Longest Subsequence With Limited Sum problem?

The time complexity is O(n log n + m log n), where n is the length of the nums array and m is the number of queries. The dominant factor is O(n log n) due to sorting the nums array.

Can the prefix sum array be reused across multiple queries?

Yes, once the nums array is sorted and the prefix sum array is computed, it can be reused for all queries, ensuring that each query is answered in logarithmic time.

What if the nums array is unsorted? Should I sort it?

Yes, sorting the nums array is necessary to optimize the solution. The sorting step ensures that we can apply binary search efficiently and answer the queries in optimal time.

How does GhostInterview help with this problem?

GhostInterview assists by providing step-by-step guidance on applying binary search and prefix sums, helping you understand how to solve the problem efficiently for multiple queries.

#2389

Easy

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

和有限的最长子序列

给你一个长度为 n 的整数数组 nums ，和一个长度为 m 的整数数组 queries 。返回一个长度为 m 的数组 answer ，其中 answer[i] 是 nums 中元素之和小于等于 queries[i] 的子序列的最大长度。子序列是由一个数组删除某些元素（也可以不删除…

数组二分查找贪心排序前缀和

题目描述

给你一个长度为 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⁶

lightbulb

解题思路

方法一：排序 + 前缀和 + 二分查找

根据题目描述，对于每个 $\textit{queries[i]}$ ，我们需要找到一个子序列，使得该子序列的元素和不超过 $\textit{queries[i]}$ ，且该子序列的长度最大化。显然，我们应该选择尽可能小的元素，这样才能使得子序列的长度最大化。

因此，我们可以先将数组 $\textit{nums}$ 进行升序排序，然后对于每个 $\textit{queries[i]}$ ，我们可以使用二分查找，找到最小的下标 $j$ ，使得 $\textit{nums}[0] + \textit{nums}[1] + \cdots + \textit{nums}[j] > \textit{queries[i]}$ 。此时 $\textit{nums}[0] + \textit{nums}[1] + \cdots + \textit{nums}[j - 1]$ 就是满足条件的子序列的元素和，且该子序列的长度为 $j$ 。因此，我们可以将 $j$ 加入答案数组中。

时间复杂度 $O((n + m) \times \log n)$ ，空间复杂度 $O(n)$ 或 $O(\log n)$ 。其中 $n$ 和 $m$ 分别是数组 $\textit{nums}$ 和 $\textit{queries}$ 的长度。

1

2

3

4

5

6

class Solution:
    def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
        nums.sort()
        s = list(accumulate(nums))
        return [bisect_right(s, q) for q in queries]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate should demonstrate an understanding of binary search applied to a sorted array.
question_mark
Look for the ability to break down the problem into subproblems like sorting and binary searching over a prefix sum.
question_mark
The candidate should highlight solving each query independently to optimize the approach.

warning

常见陷阱

外企场景

error
Overlooking the importance of sorting the array before attempting to answer queries efficiently.
error
Incorrectly implementing binary search, leading to incorrect subsequences being selected for each query.
error
Neglecting the need to compute prefix sums, which is essential for optimizing the solution.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Adjust the problem to find subsequences with a sum strictly less than the query value.
arrow_right_alt
Allow for multiple queries to be processed simultaneously using a more advanced algorithm like a segment tree.
arrow_right_alt
Modify the problem to return the sum of the largest subsequence instead of its size.

help

常见问题

外企场景

继续练习

#2448 使数组相等的最小开销 #2271 毯子覆盖的最多白色砖块数 #2234 花园的最大总美丽值