来自 Codility 的 TapeEquilibrium 任务，未能通过 100% 测试、性能和正确性（总分 76%）

Question

抱歉我写的太多了。我试图非常详细，以便在描述问题（解决方案，以及我如何到达那里）时找到自己的答案，但是，如果我没有，不要给 reader 留下疑问。我不想让其他人解决这个问题，只要得到一些指示，如果可能的话，我应该在哪里改进我的解决方案。如果这种方法不正确，我愿意放弃它，但我也很想使这种方法通过 100%，如果可能的话，如果它有意义并且适合 effort-quality 关系.如果我的想法不好，我不介意被告知并跟随另一个，但是再次强调，请不要向我展示代码或 "right answer"，我可以 google 自己或在此处找到它所以。
练习是这样的：

A non-empty array A consisting of N integers is given. Array A represents numbers on a tape.

Any integer P, such that 0 < P < N, splits this tape into two non-empty parts:

 A[0], A[1], ..., A[P − 1] and A[P], A[P + 1], ..., A[N − 1].

The difference between the two parts is the value of:

|(A[0] + A[1] + ... + A[P − 1]) − (A[P] + A[P + 1] + ... + A[N − 1])|

In other words, it is the absolute difference between the sum of the first part and the sum of the second part.

For example, consider array A such that:

A[0] = 3 A[1] = 1 A[2] = 2 A[3] = 4 A[4] = 3

We can split this tape in four places:

P = 1, difference = |3 − 10| = 7
P = 2, difference = |4 − 9| = 5
P = 3, difference = |6 − 7| = 1
P = 4, difference = |10 − 3| = 7

Write a function:

class Solution { public int solution(int[] A); }

that, given a non-empty array A of N integers, returns the minimal difference that can be achieved.

For example, given:

A[0] = 3 A[1] = 1 A[2] = 2 A[3] = 4 A[4] = 3

the function should return 1, as explained above.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [2..100,000]; each element of array A is an integer within the range [−1,000..1,000].

如标题所述，我的解决方案不是很好（性能 66%；正确性 85%；总分 76%）。
这是我昨天使用的方法：

accumulate from the left and the right side of the array received, and check which side would be smaller after adding the next one to the right of the left side, or the nearest to the left of the right side of the array.
Graphically, the idea was sort of making two trains: first the locomotives (head and tail of the array, respectively) of each side, and then add to each locomotive the train wagons (if any, and if it corresponded to), and make both trains crash. I was sort of "adding wagons to a train, only if the other train was bigger than the one I added a wagon to last".
The code I wrote didn't work that well, because I needed to find the smallest difference I could between the two partitions of the array.

但我从中得到了几个错误：负数与 non-negative 混合，两个元素数组等，甚至更糟糕的结果（如总分的 65%）。
这个想法和我今天遵循的想法相似：

Accumulate from the left and the right side, and check if the difference between the left and the right trains was smaller after adding a wagon to the left, or to the right. In this approach I concentrated in the "difference between the two trains, and not in adding a wagon if the other one was bigger and find an equilibrium".

无论如何，我在以下方面遇到了错误：

small_random：随机小，长度 = 100：错误答案，得到 269 预期 39
large_ones：大序列，从-1到1的数字，长度=~100,000：错误答案，得到228个预期的0；错误答案，得到 147 个预期 1。（可能溢出？）
large_random 随机大，长度 = ~100,000：错误答案，得到 202635 预期 1；错误答案，预期得到 34394 2

所有其他测试都很好。这是我写的代码：

using System;

class Solution {
    public int solution(int[] A)
    {
        int N = A.Length, P;
        if (N == 0)
        {
             P = 0;
        }
        else
        {
            P = findTapeEquilibrium(A, N);
        }
        return P;
    }

    private static int findTapeEquilibrium(int[] A, int N)
    {
        int I = 0, J = N - 1;
        if( N > 0 )
        {
            int leftP = A[I++], rightP = A[J--];
            bool AIsPair = N - 1 % 2 == 0;
            while((!AIsPair &&  J - I >= 0) || (AIsPair && J - I >= 1))
            {
                if (Math.Abs((leftP+A[I])-rightP) <= Math.Abs(leftP-(rightP+A[J])))
                {
                    leftP += A[I++];
                }
                else
                {
                    rightP += A[J--];
                }
            }
            return Math.Abs(leftP - rightP);
        }
        return 0;
    }
}

Answer 1

所以，我最后看了yusheng123的解决方案，在python，但是他的代码很容易理解。
现在我意识到我做的事情很糟糕：我试图调试或修复一个考虑不周的解决方案。
这个人的解决方案，和我最后的解决方案有点相似，但是有很大的不同。
我正在比较数组的第一个和最后一个元素，然后将数字添加到头部或尾部（累加器），这取决于两者之间的差异是否会更小，这太糟糕了：太复杂了，太专注于收到的结构，最重要的是，没有从数组本身（分区！）中抽象出自己来找到解决问题的正确方法：你必须找到那些分区的事实并不意味着你有实际上有点创建你自己的两个数组，即使我从两端积累，我现在看到它与问题本身根本没有分离，我本身并不是在创建数组，但实现它的过程是我的低能方法也是如此。
相反，如果我强调头部（仅是第一个元素）和尾部（数组中所有其他元素的总和）之间的区别，那么我在更高的抽象级别，以及我可以从头到尾遍历数组并找到解决方案的事实，并列说明了很多。
所以，在未来，当我看到自己在做与我所做的类似的事情时，我会对我说："How can you follow a simpler plan (a simpler iteration in this particular case) and still content yourself by following the idea you thought of but not pushing it too hard (as I did in this case)? Don't throw your idea to the garbage yet, discard your complicated code though, make it simpler, and try to isolate the, maybe plausible idea from the implementation for now, until you find something that clicks in your mind, since many rules, and questions have to be asked to accomplish what you are trying to."如果我用这个答案来对未来的自己说话，请原谅我不完全谈论代码本身。
继续我在网上找到的绝妙解决方案，该策略（将头部设置为数组的第一个元素，将尾部设置为数组其余部分的总和）将继续设置为初始最小差的值，到头部与其余元素之和之间的值，然后你只需遍历数组，并将当前元素添加到头部累加器，并从其余（尾部累加器）中减少该值，同时检查这两者之间的新差异是否小于开始时保存的差异，那么它应该被新值覆盖（这就是我们想要的首先找到，这是函数将在末尾 return 或在开头（如果数组中有 0、1 或 2 个元素）的值。
机车上没有货车（我现在明白我在你自己的声音中听起来是多么愚蠢，默读我写的东西）。在这个简单问题中不需要这么愚蠢的类比，有这样一个简单和优雅解决方案。就在那里：我将能够发现我在类似情况下做错事的未来。
这种方法有很多顺序。更高层次的抽象。如果有错误，它们将很容易找到，依此类推。这是 "my" 最终代码。

public int solution(int[] A)
{
    int head = A[0], tail = A.Sum() - head;
    int min_diff = Math.Abs(head - tail);
    for (int i = 1; i < A.Length; i++)
    {
        if (Math.Abs(head - tail) < min_diff)
            min_diff = Math.Abs(head - tail);
        head += A[i];
        tail -= A[i];
    }
    return min_diff;
}

当然，这个方案的最终分数是100%。就是这么美丽和简单。

来自 Codility 的 TapeEquilibrium 任务，未能通过 100% 测试、性能和正确性（总分 76%）

TapeEquilibrium task from Codility, failing to pass 100% tests, performance and correctness (76% total score)

c#

arrays

overflow

array-difference

difference