java - 找到加起来等于给定总和的最小子数组(允许重复)

Question

我想找到加起来等于给定目标的最小子数组。
我的输入是输入array 和目标sum.

我知道这个问题已经被问过很多次，但在大多数情况下，人们试图找到所有可能的组合来达到他们的目标，或者他们的解决方案不允许重复。

在我的例子中，我想仅找到最小的子数组，并且允许从输入数组中复制数据。

例如，给定输入数组 [1,4,10,20,35] 和目标 17，我希望输出数组为[10,4,1,1,1]。
因此，我的算法可以在查找输出时复制输入数组中的任何值。

这是我目前所拥有的:

public static ArrayList<Integer> representNumberAsSumOfArrayElements(ArrayList<Integer> inputs, int target)
{
    ArrayList<Integer> result = new ArrayList<>();

    //First sort the input array in descending order
    Collections.sort(inputs, Collections.reverseOrder());
    int i = 0;

    //Iterate through the input array and break down the target into a sum of the input array
    while (i < inputs.size() && target > 0) {
        if(target >= inputs.get(i) ) {
            result.add(inputs.get(i));
            target = target - inputs.get(i);
        } else {
            i++;
        }
    }
    return result;
}

只是一个简单的驱动程序来测试 100 个目标上的代码:

public static void main(String[] args) {
    ArrayList<Integer> inputs = new ArrayList<>(Arrays.asList( 1, 4, 10, 20, 35, 56, 84));
    int n = 100;
    ArrayList<Integer> sumArray = new ArrayList<>();
    for (int i = 0; i <= n; i++)
    {
        sumArray = representNumberAsSumOfArrayElements(inputs, i); // O(n)
        System.out.println(i + " written as a sum of array elements " + sumArray);
    }
}

我已经实现了适用于大多数值的 O(n) 算法，但在某些情况下，我得到了错误的结果。
例如，当我使用 [1,4,10,20,35,56,84] 的输入和 69 的目标总和运行我的代码时，正确的输出将是 [35,20,10,4] 但我的算法输出 [56,10,1,1,1]。
我明白为什么我的算法是错误的，但我不确定如何修复它。

Answer 1

首先创建一个前缀总和数组，使得 prefSum[i] 给出给定数组中从索引 0 到 i(包括两者)的所有元素的总和。如果您的数组包含所有正整数，则 prefSum 数组已排序，您可以做二进制搜索。所以扫描 prefSum 数组从 0 到 length 并在 0 到 (i-1) 之间进行二进制搜索如果您当前的索引是 i 并尝试找到最大的 j其中 j 在 0 到 i-1 之间这样 prefSum[i]-prefSum[j]=given 目标。总体复杂度为 nlogn。