2022-06-16：给定一个数组arr，含有n个数字，都是非负数，
给定一个正数k，
返回所有子序列中，累加和最小的前k个子序列累加和。
假设K不大，怎么算最快？
来自亚马逊。
答案2022-06-16：
排序，小根堆。
代码用rust编写。代码如下：
代码语言：javascript复制fn main() {
let mut nums: Vec<i32> = vec![6, 19, 3, 8, 29];
let ans = top_min_sum2(&mut nums, 3);
println!("ans = {:?}", ans);
}
fn top_min_sum2(arr: &mut Vec<i32>, k: i32) -> Vec<i32> {
arr.sort();
// (最右的下标，集合的累加和)
let mut heap: Vec<Vec<i32>> = vec![];
heap.push(vec![0, arr[0]]);
let mut ans: Vec<i32> = vec![];
for _ in 0..k {
ans.push(0);
}
// ans[0] = 0
// 0 1 2 k-1
// k个！
for i in 1..k {
heap.sort_by(|a, b| b[1].cmp(&a[1]));
let cur = heap.pop().unwrap();
// (7, 100)
// 左 ：8, 100 - arr[7] arr[8]
// 右 ：8， 100 arr[8]
let last = cur[0];
let sum = cur[1];
ans[i as usize] = sum;
if last 1 < arr.len() as i32 {
heap.push(vec![
last 1,
sum - arr[last as usize] arr[(last 1) as usize],
]);
heap.push(vec![last 1, sum arr[(last 1) as usize]]);
}
}
return ans;
}执行结果如下：
***
[左神java代码](https://github.com/algorithmzuo/weekly-problems/blob/main/src/class_2022_04_1_week/Code06_TopMinSubsquenceSum.java)
