时间戳

首页 > 解决方案 > 查找加起来等于给定总和的最小子数组（允许重复）

java - 查找加起来等于给定总和的最小子数组（允许重复）

问题描述

我想找到加到给定目标的最小子数组。
我的输入是输入数组和目标总和。

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

就我而言，我只想找到最小的子数组，并且允许从输入数组复制数据。

例如，给定一个 的输入数组[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]。
我理解为什么我的算法是错误的，但我不知道如何解决它。

标签： javaarraysalgorithm

解决方案

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

推荐阅读