给你一个长度为 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
方法一:排序 + 前缀和 + 二分查找
根据题目描述,对于每个
因此,我们可以先将数组
时间复杂度
方法二:排序 + 离线查询 + 双指针
与方法一类似,我们可以先对数组
接下来,我们定义一个长度与
我们使用一个变量
我们遍历下标数组
遍历完下标数组
时间复杂度
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]
class Solution:
def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
nums.sort()
m = len(queries)
ans = [0] * m
idx = sorted(range(m), key=lambda i: queries[i])
s = j = 0
for i in idx:
while j < len(nums) and s + nums[j] <= queries[i]:
s += nums[j]
j += 1
ans[i] = j
return ans
class Solution {
public int[] answerQueries(int[] nums, int[] queries) {
Arrays.sort(nums);
for (int i = 1; i < nums.length; ++i) {
nums[i] += nums[i - 1];
}
int m = queries.length;
int[] ans = new int[m];
for (int i = 0; i < m; ++i) {
ans[i] = search(nums, queries[i]);
}
return ans;
}
private int search(int[] nums, int x) {
int l = 0, r = nums.length;
while (l < r) {
int mid = (l + r) >> 1;
if (nums[mid] > x) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
}
class Solution {
public int[] answerQueries(int[] nums, int[] queries) {
Arrays.sort(nums);
int m = queries.length;
Integer[] idx = new Integer[m];
for (int i = 0; i < m; ++i) {
idx[i] = i;
}
Arrays.sort(idx, (i, j) -> queries[i] - queries[j]);
int[] ans = new int[m];
int s = 0, j = 0;
for (int i : idx) {
while (j < nums.length && s + nums[j] <= queries[i]) {
s += nums[j++];
}
ans[i] = j;
}
return ans;
}
}
class Solution {
public:
vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {
sort(nums.begin(), nums.end());
for (int i = 1; i < nums.size(); i++) {
nums[i] += nums[i - 1];
}
vector<int> ans;
for (auto& q : queries) {
ans.push_back(upper_bound(nums.begin(), nums.end(), q) - nums.begin());
}
return ans;
}
};
class Solution {
public:
vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {
sort(nums.begin(), nums.end());
int m = queries.size();
vector<int> idx(m);
iota(idx.begin(), idx.end(), 0);
sort(idx.begin(), idx.end(), [&](int i, int j) {
return queries[i] < queries[j];
});
vector<int> ans(m);
int s = 0, j = 0;
for (int i : idx) {
while (j < nums.size() && s + nums[j] <= queries[i]) {
s += nums[j++];
}
ans[i] = j;
}
return ans;
}
};
func answerQueries(nums []int, queries []int) (ans []int) {
sort.Ints(nums)
for i := 1; i < len(nums); i++ {
nums[i] += nums[i-1]
}
for _, q := range queries {
ans = append(ans, sort.SearchInts(nums, q+1))
}
return
}
func answerQueries(nums []int, queries []int) (ans []int) {
sort.Ints(nums)
m := len(queries)
idx := make([]int, m)
for i := range idx {
idx[i] = i
}
sort.Slice(idx, func(i, j int) bool { return queries[idx[i]] < queries[idx[j]] })
ans = make([]int, m)
s, j := 0, 0
for _, i := range idx {
for j < len(nums) && s+nums[j] <= queries[i] {
s += nums[j]
j++
}
ans[i] = j
}
return
}
function answerQueries(nums: number[], queries: number[]): number[] {
nums.sort((a, b) => a - b);
for (let i = 1; i < nums.length; i++) {
nums[i] += nums[i - 1];
}
const ans: number[] = [];
const search = (nums: number[], x: number) => {
let l = 0;
let r = nums.length;
while (l < r) {
const mid = (l + r) >> 1;
if (nums[mid] > x) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
};
for (const q of queries) {
ans.push(search(nums, q));
}
return ans;
}
function answerQueries(nums: number[], queries: number[]): number[] {
nums.sort((a, b) => a - b);
const m = queries.length;
const idx: number[] = new Array(m);
for (let i = 0; i < m; i++) {
idx[i] = i;
}
idx.sort((i, j) => queries[i] - queries[j]);
const ans: number[] = new Array(m);
let s = 0;
let j = 0;
for (const i of idx) {
while (j < nums.length && s + nums[j] <= queries[i]) {
s += nums[j++];
}
ans[i] = j;
}
return ans;
}
impl Solution {
pub fn answer_queries(mut nums: Vec<i32>, queries: Vec<i32>) -> Vec<i32> {
let n = nums.len();
nums.sort();
queries
.into_iter()
.map(|query| {
let mut sum = 0;
for i in 0..n {
sum += nums[i];
if sum > query {
return i as i32;
}
}
n as i32
})
.collect()
}
}