carloscn
commented
11 months ago Analysis
pub fn answer_queries(nums: Vec<i32>, queries: Vec<i32>) -> Vec<i32>
{
let mut ret:Vec<i32> = vec![];
if nums.len() < 1 || queries.len() < 1 {
return ret;
}
let mut nums_dup = nums.clone();
// [1] sort input values in place
nums_dup.sort_unstable();
// [2] compute cumsums in place
let mut acc = 0;
let sums: Vec<i32> = nums_dup.into_iter().map(|num| { acc += num; acc }).collect::<Vec<i32>>();
// [3] for a sorted list of cumsums, we can quickly find the index using binary search
ret = queries.into_iter().map(|q| match sums.binary_search(&q) {
Ok(i) => i + 1,
Err(i) => i,
} as i32).collect::<Vec<_>>();
return ret;
}
Description
You are given an integer array nums of length n, and an integer array queries of length m.
Return an array answer of length m where answer[i] is the maximum size of a subsequence that you can take from nums such that the sum of its elements is less than or equal to queries[i].
A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.
Example 1:
Input: nums = [4,5,2,1], queries = [3,10,21] Output: [2,3,4] Explanation: We answer the queries as follows:
Example 2:
Input: nums = [2,3,4,5], queries = [1] Output: [0] Explanation: The empty subsequence is the only subsequence that has a sum less than or equal to 1, so answer[0] = 0.
Constraints:
n == nums.length m == queries.length 1 <= n, m <= 1000 1 <= nums[i], queries[i] <= 106