2022-06-16：给定一个数组arr，含有n个数字，都是非负数， 给定一个正数k， 返回所有子序列中，累加和最小的前k个子序列累加和。 假设K不大，怎么算最快？ 来自亚马逊。

2022-06-16：给定一个数组arr，含有n个数字，都是非负数，
给定一个正数k，
返回所有子序列中，累加和最小的前k个子序列累加和。
假设K不大，怎么算最快？
来自亚马逊。

答案2022-06-16：

排序，小根堆。

代码用rust编写。代码如下：

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代码

2022-06-16：给定一个数组arr，含有n个数字，都是非负数， 给定一个正数k， 返回所有子序列中，累加和最小的前k个子序列累加和。 假设K不大，怎么算最快？ 来自亚马逊。的相关教程结束。