java - 迭代和递归解决方案的时间复杂度

Question

我正在尝试解决以下问题:

我觉得我已经对它进行了很多思考并尝试了很多东西。我设法解决了它，并产生了正确的值，但问题是它的时间效率不够高。它完成了 Kattis 测试中的 2 个，但由于超过了 1 秒的时间限制，第 3 个失败了。恐怕我无法看到他们测试的输入是什么。

我从一个递归解决方案开始并完成了它。但后来我意识到它的时间效率不够高，所以我尝试改用迭代解决方案。

我从读取输入开始并将它们添加到 ArrayList。然后我调用以下方法，目标为 1000。

public static int getCorrectWeight(List<Integer> platesArr, int target) {
    /* Creates two lists, one for storing completed values after each iteration,
    one for storing new values during iteration. */
    List<Integer> vals = new ArrayList<>();
    List<Integer> newVals = new ArrayList<>();

    // Inserts 0 as a first value so that we can start the first iteration.
    int best = 0;
    vals.add(best);

    for(int i=0; i < platesArr.size(); i++) {
        for(int j=0; j < vals.size(); j++) {
            int newVal = vals.get(j) + platesArr.get(i);
            if (newVal <= target) {
                newVals.add(newVal);
                if (newVal > best) {
                    best = newVal;
                }
            } else if ((Math.abs(target-newVal) < Math.abs(target-best)) || (Math.abs(target-newVal) == Math.abs(target-best) && newVal > best)) {
                best = newVal;
            }
        }
        vals.addAll(newVals);
    }
    return best;
}

我的问题是，有没有什么方法可以降低大量数据的时间复杂度？

Answer 1

主要问题是 vals 和 newVals 的大小会增长得非常快，因为每次迭代都会使它们的大小加倍。您只需要存储 1000 个左右应该易于管理的值。您正在限制这些值，但因为它们存储在 ArrayList 中，所以最终会出现很多重复值。

如果相反，您使用了 HashSet，那么它应该对效率有很大帮助。