Определение, если соседи значения в массиве складываются до заданного значения?

Question

Я делаю простую сложную математическую игру, и мне было интересно, как реализовать следующее:

Скажем, у меня есть этот массив:

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

и я хотите, чтобы пользователь вставил значение, скажем, 2 где-нибудь в массиве, чтобы набор последовательно помещенных чисел в массиве , включая вновь помещенное значение , складывалось в целевое значение, скажем, 8. Я назову эту комбинацию чисел combo .

Я хочу, чтобы пользователь мог разместить 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 - значение). Это те индексы, которые вы ищете. Причина, по которой я не считаю введенное значение для сумм, заключается в том, что это приведет к его двойному счету; его проще добавить после факта.

Полезная часть этого заключается в том, что вы всегда проверяете только введенное значение. Рассмотрим следующий пример, все еще ища 8:

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

становится

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

Хотя ваш массив по-прежнему имеет 9 значений, вы уже знаете, что у вас осталось только 6 из них проверьте.