给你一个长度为 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.lengthm == queries.length1 <= n, m <= 10001 <= nums[i], queries[i] <= 106
方法一：二分查找
由题意可知，nums 的元素次序对结果无影响，因此我们对 nums 从小到大进行排序。显然和有限的最长子序列由最小的前几个数组成。使用数组 f 保存 nums 的前缀和，其中 f[i] 表示前 i 个元素之和（不包括 nums}[i]）。遍历 queries，假设当前查询值为 q，使用二分查找获取满足 f[i] \gt q 的最小的 i，那么和小于等于 q 的最长子序列长度为 i-1。
[sol1-Python3]1
2
3
4
| class Solution:
def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
f = list(accumulate(sorted(nums)))
return [bisect_right(f, q) for q in queries]
|
[sol1-C++]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {
int n = nums.size(), m = queries.size();
sort(nums.begin(), nums.end());
vector<int> f(n + 1);
for (int i = 0; i < n; i++) {
f[i + 1] = f[i] + nums[i];
}
vector<int> answer(m);
for (int i = 0; i < m; i++) {
answer[i] = upper_bound(f.begin(), f.end(), queries[i]) - f.begin() - 1;
}
return answer;
}
};
|
[sol1-Java]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
public int[] answerQueries(int[] nums, int[] queries) {
int n = nums.length, m = queries.length;
Arrays.sort(nums);
int[] f = new int[n + 1];
for (int i = 0; i < n; i++) {
f[i + 1] = f[i] + nums[i];
}
int[] answer = new int[m];
for (int i = 0; i < m; i++) {
answer[i] = binarySearch(f, queries[i]) - 1;
}
return answer;
}
public int binarySearch(int[] f, int target) {
int low = 1, high = f.length;
while (low < high) {
int mid = low + (high - low) / 2;
if (f[mid] > target) {
high = mid;
} else {
low = mid + 1;
}
}
return low;
}
}
|
[sol1-C#]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| public class Solution {
public int[] AnswerQueries(int[] nums, int[] queries) {
int n = nums.Length, m = queries.Length;
Array.Sort(nums);
int[] f = new int[n + 1];
for (int i = 0; i < n; i++) {
f[i + 1] = f[i] + nums[i];
}
int[] answer = new int[m];
for (int i = 0; i < m; i++) {
answer[i] = BinarySearch(f, queries[i]) - 1;
}
return answer;
}
public int BinarySearch(int[] f, int target) {
int low = 1, high = f.Length;
while (low < high) {
int mid = low + (high - low) / 2;
if (f[mid] > target) {
high = mid;
} else {
low = mid + 1;
}
}
return low;
}
}
|
[sol1-C]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| static int cmp(const void *pa, const void *pb) {
return *(int *)pa - *(int *)pb;
}
int binarySearch(int *arr, int arrSize, int target) {
int low = 1, high = arrSize;
while (low < high) {
int mid = low + (high - low) / 2;
if (arr[mid] > target) {
high = mid;
} else {
low = mid + 1;
}
}
return low;
}
int* answerQueries(int* nums, int numsSize, int* queries, int queriesSize, int* returnSize) {
qsort(nums, numsSize, sizeof(int), cmp);
int f[numsSize + 1];
f[0] = 0;
for (int i = 0; i < numsSize; i++) {
f[i + 1] = f[i] + nums[i];
}
int *answer = (int *)calloc(sizeof(int), queriesSize);
for (int i = 0; i < queriesSize; i++) {
answer[i] = binarySearch(f, numsSize + 1, queries[i]) - 1;
}
*returnSize = queriesSize;
return answer;
}
|
[sol1-JavaScript]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| var answerQueries = function(nums, queries) {
const n = nums.length, m = queries.length;
nums.sort((a, b) => a - b);
const f = new Array(n + 1).fill(0);
for (let i = 0; i < n; i++) {
f[i + 1] = f[i] + nums[i];
}
const answer = new Array(m).fill(0);
for (let i = 0; i < m; i++) {
answer[i] = binarySearch(f, queries[i]) - 1;
}
return answer;
}
const binarySearch = (f, target) => {
let low = 1, high = f.length;
while (low < high) {
const mid = low + Math.floor((high - low) / 2);
if (f[mid] > target) {
high = mid;
} else {
low = mid + 1;
}
}
return low;
};
|
[sol1-Golang]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| func answerQueries(nums []int, queries []int) []int {
sort.Ints(nums)
n := len(nums)
f := make([]int, n)
f[0] = nums[0]
for i := 1; i < n; i++ {
f[i] = f[i-1] + nums[i]
}
ans := []int{}
for _, q := range queries {
idx := sort.SearchInts(f, q+1)
ans = append(ans, idx)
}
return ans
}
|
复杂度分析
