java - 确定数组中某个值的邻居之和是否等于设定值？

Question

我正在制作一个简单的加法数学游戏，并且想知道如何实现以下内容。

假设我有这个数组:

int[] numbers = { 9, 2, 1, 1, 2, 9 };

我希望用户在数组中的某个位置插入一个值，例如 2，以便数组中的一堆连续放置数字包括新放置的值 添加目标值，例如 8 。我将这个数字组合称为组合。

我希望用户能够将 8 放置在该数组中的任何位置。由于 2 + 1 + 1 + 2 = 6 用户应该能够将其放置在外部 9 之间的任何位置。

例如，正确的位置可以是 {9, 2, *2*, 1, 1, 2, 9} 或 {9, *2*, 2, 1, 1, 2, 9}。

现在我实现这个的问题是，只有当您将 2 放在组合的外侧时，我才能让它工作，所以就像本段上面的第二个示例一样，与第一个不同。

我这样做的方法是:

1. 从数组的 startIndex 处查找值
2. 将此值添加到 currentSum
3. 查看是否找到 currentSum == targetValue:组合
4. 否则如果 currentSum > targetValue :未找到组合
5. 否则设置 startIndex += 1(如果放置在另一端则设置为 -1)并重复

但这只能解决当新放置的值位于组合的外部边界时的问题。

我意识到我可以通过将包含新放置的值的每个潜在子数组的内容相加，然后查看其中一个加起来是否达到目标值 8 来暴力解决这个问题，但我正在寻找更优雅的东西。

Answer 1

您可以通过在填充值的左侧和右侧创建一个求和数组来实现此目的，一旦达到(或超过)目标就停止计算。在本例中，我使用 -1 来标记不需要考虑的值。考虑你的例子:

nums = { 9, 2, *2*, 1, 1, 2, 9 }

变成了

sums = { -1, 2, 0, 1, 2, 4, -1 }

现在，您可以在此序列中找到 (8 - 值)，这意味着您插入的值位于开头或结尾，或者是插入索引右侧和左侧的两个值的组合，总计为 (8 - 值(value))。这些是您正在寻找的索引。我不计算总和中插入值的原因是，这会导致它被计算为双倍；事后添加会更容易。

这样做的有用部分是您始终只检查插入的值。 考虑下一个例子，仍然寻找 8:

nums = { 3, 4, 3, *2*, 1, 2, 4, 1, 5 }

变成了

sums = { -1, 7, 3, *0*, 1, 3, 7, -1, -1 }

虽然您的数组仍然有 9 个值长，但您已经知道只剩下 6 个值需要检查。