Индекс равновесия - что не так с моим решением?

Question

Я прошел этот пример теста , прежде чем попробую взять настоящий для собеседования.Задача состоит в том, чтобы правильно реализовать задачу Equilibrium Index .
Я кодировал какое-то решение, которое работает только для простого примера и некоторых крайних случаев.
Вот код:

typedef vector<int> container_t;
typedef container_t::const_iterator iterator_t;

int find_equilibrium(const container_t &A);

int equi (const container_t &A)
{
    const std::size_t length = A.size();
    if (length  == 0)
        return -1;

    if (length == 1 && A[0] == 0)
        return -1;

    if (length == 1 && A[0] != 0)
        return 0;

    return find_equilibrium(A);
}

int find_equilibrium(const container_t &A)
{
    unsigned int i = 0;
    int sum = 0;

    for (iterator_t iter = A.begin(); iter != A.end(); ++iter, ++i)
    {
        sum += *iter; // not using std::accumulate to avoid N^2

        if (sum == 0)
            return i + 1;
    }

    return -1;
}

Это, однако, фатально некорректно для таких случаев, как [2, -2].Однако по какой-то причине исключается исключение arithmetic_overflow.После Google, я обнаружил, что алгоритм отличается от моего:

#include <numeric>
typedef vector<int> container_t;
typedef container_t::const_iterator iterator_t;

int find_equilibrium(const container_t &A);

int equi (const container_t &A)
{
    const std::size_t length = A.size();
    if (length  == 0)
        return -1;

    if (length == 1)
        return 0;

    return find_equilibrium(A);
}

int find_equilibrium(const container_t &A)
{
  unsigned int i = 0;
  int left = 0, right = std::accumulate(A.begin(), A.end(), 0);

  for (iterator_t iter = A.begin(); iter != A.end(); ++iter, ++i)
  {
    right -= *iter;

    if (left == right)
      return i;

    left += *iter;
  }

  return -1;
}

Этот код не работает с очень большими числами, но работает иначе.Я понятия не имею, почему, хотя.

Мои вопросы:

• Что не так с тем, как я подходил к этому, и как я могу подойти к другому вопросу такого типа более правильно в течение 30 минут?
• Что на самом деле являются всеми угловыми случаями именно для этой проблемы?
• Как набрать 100 баллов за этот пример теста?

Answer 1

Ваша логика верна.

A [0] + A [1] + A [2] = A [3] + A [4] + A [5] эквивалентно A [0] + A [1] + A [2] - (A [3] + A [4] + A [5]) = 0

Однако, в вашем коде, в цикле вы постоянно добавляете значения, вы никогда не меняете знак для тех в другой половине.

for (iterator_t iter = A.begin(); iter != A.end(); ++iter, ++i) {
  sum += *iter; // only increasing, where do you subtract the values of the second half?
  if (sum == 0)
    return i + 1; // from the initial value you return the next index that gives you zero sum
}