我正在考虑如何用额外的约束来解决子集和问题:数组的子集需要连续(索引需要)。我试图解决它使用递归在Java.
我知道非约束问题的解决方案:每个元素可以在子集中(因此我对sum = sum - arr[index]执行递归调用)，也可以不在子集中(因此我对sum = sum执行递归调用)。
我正在考虑是否添加另一个参数来了解天气或之前的索引是否是子集的一部分，但我不知道下一步该怎么做。
你做对了。
这样想:
- 对于每个条目，你必须决定:你是想在此时开始一个新的总和，还是跳过它并重新考虑下一个条目。
a + b + c + d包含b + c + d的和。你想重新计算一下这些总和吗?- 也许自下而上的方法会更好
您要求的O(n)解决方案:
该方案需要三个不动点数:起始索引和结束索引，以及span
的总和。从元素0开始(如果您愿意，也可以从列表末尾开始)增加结束索引，直到总和大于或等于所需值。如果它们相等，你就得到了一个子集和。如果它更大，则将开始索引向上移动一个并减去前一个开始索引的值。最后，如果结果的总和大于期望的值，则将结束索引移回，直到总和小于期望的值。在另一种情况下(总和较小)，将结束索引向前移动，直到总和大于所需值。如果没有找到匹配项，重复
所以,警告:
- 这"相当明显"吗?也许是，也许不是。当我说两者"相当明显"时，我是在假设相似性的数量级。和0 (n)在我的评论
- 这实际上是0 (n)吗?这在很大程度上取决于列表中数字的相似程度(就数量级(数字中的位数)而言)。所有数字之间的距离越近，在end索引上测试子集是否存在所需的步骤就越少。另一方面，如果你有几个非常大的数字(比如几千)被数百个非常小的数字(1、2和3)包围我给出的解决方案将更接近于O(n^2)
- 此解决方案仅适用于您的限制，即子集值是连续的