题目
给你一个长度为 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^6
解题
方法一:排序 前缀和 二分查找
思路
首先,要求的是子序列的最大长度,因为子序列可以通过增删元素得到,也就意味着数组可以排序,而子序列的最大长度又与子序列的和有关,所以应该先把数组升序排序。
然后问题就变成了求 nums
中元素之和小于等于 queries[i]
的前缀子数组的最大长度,这里提到了子数组元素之和,自然可以想到用前缀和求解,于是构造数组的前缀和数组。
那么问题就变成了求**前缀和数组**中小于等于 queries[i]
的元素中最靠右的位置。在有序数组中求元素位置可以使用二分查找进行优化,具体需要用到:二分查找 - 整数二分 - 小于等于。
求出位置后覆盖 queries
数组最后返回即可。
代码
class Solution {
public int[] answerQueries(int[] nums, int[] queries) {
Arrays.sort(nums);
int n = nums.length;
int[] prefixSums = new int[n + 1];
for (int i = 1; i <= n; ++i) {
prefixSums[i] = nums[i - 1] + prefixSums[i - 1];
}
for (int i = 0; i < queries.length; ++i) {
int query = queries[i];
int l = 0, r = n;
while (l < r) {
int c = l + r + 1 >> 1;
if (prefixSums[c] <= query) l = c;
else r = c - 1;
}
queries[i] = l;
}
return queries;
}
}
class Solution {
public:
vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {
sort(nums.begin(), nums.end());
int n = nums.size();
vector<int> prefix_sums(n + 1);
for (int i = 0; i < n; ++i) {
prefix_sums[i + 1] = prefix_sums[i] + nums[i];
}
for (int& query : queries) {
query = upper_bound(prefix_sums.begin(), prefix_sums.end(), query)- prefix_sums.begin() - 1;
}
return queries;
}
};
评论区