一、题目描述
原题连接： 2389. 和有限的最长子序列
题目描述：
给你一个长度为 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] <= 106
二、解题
1、方法——二分法
1.1、思路分析
由题目描述我们可知，对于每个queries[i]，我们都需要找到一个子序列，使得该子序列的元素之和不超过queries[i]，
且要使得该子序列的长度最大化，很显然，我们应该尽量选择较小的元素，这样才能使得子序列的长度最大化。
所以我们可以先对nums数组进行排序，然后使用一个数组f来保存nums数组的前缀和，f[i]保存的是数组nums从下标位0到下标位i - 1的元素的和：
所以f数组的长度要比nums数组的长度要大1。
然后我们顺序遍历queries数组，对于每个queries[i]，都使用二分查找法在f数组中查找到第一个大于queries[i]的元素，
如果该元素的下标为x，那么x - 1就为对应的最长子序列的长度
1.2、代码实现
有了以上思路，那我们写起代码来也就水到渠成了：文章来源：https://www.toymoban.com/news/detail-415075.html
// 先写一个函数，比较两个整数的大小
int cmp_int(const void* p1, const void* p2) {
assert(p1 && p2);
return *((int*)p1) - *((int*)p2);
}
// 再写一个二分查找算法
int binary_search(int left, int right, int* nums, int target) {
assert(nums);
int mid = 0;
while (left < right) {
if (nums[left] > target) {
return left;
}
mid = left + (right - left) / 2;
if (nums[mid] <= target) {
left = mid + 1;
}
else {
right = mid;
}
}
return left;
}
int* answerQueries(int* nums, int numsSize, int* queries, int queriesSize, int* returnSize) {
assert(nums && queries && returnSize);
// 先对nums数组进行排序
qsort(nums, numsSize, sizeof(int), cmp_int);
int* answer = (int*)malloc(queriesSize * sizeof(int));
*returnSize = queriesSize;
if (NULL == answer) {
perror("malloc");
return NULL;
}
int* f = (int*)malloc((numsSize + 1) * sizeof(int));
if (NULL == f) {
perror("malloc");
return NULL;
}
int i = 0;
int j = 0;
int sum = 0;
// 求前缀和
for (i = 0; i < numsSize + 1; i++) {
f[i] = sum;
if (i < numsSize) {
sum += nums[i];
}
}
for (i = 0; i < queriesSize; i++) {
answer[i] = binary_search(0, numsSize + 1, f, queries[i]) - 1;
}
free(f);
f = NULL;
return answer;
}
时间复杂度：O((n+m)logn)，其中n为数组nums的长度，m为数组queries的长度，对数组nums进行排序的复杂度为nlogn，二分查找的复杂度为logn，故总的时间复杂度为O((n+m)logn)。
空间复杂度：O(n + m)。我们总共需要n + m + 1个额外空间，故空间复杂度为O(n + m)。文章来源地址https://www.toymoban.com/news/detail-415075.html
到了这里，关于【刷题之路】LeetCode 2389. 和有限的最长子序列的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
