均衡指数 - 我的解决方案有什么问题？

Question

在我尝试采用真实的面试之前,我已经采用了这个例子测试.面临的挑战是正确实施均衡指数问题.
我编写了某种解决方案,仅适用于简单示例和一些边缘情况.
这是代码:

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异常.谷歌搜索后,我发现算法与我自己的算法不同:

#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
}