找到许多方法来产生相等的总和？

Question

所以，我试图解决这个问题：

你得到了数组a[1]， a【2】， ..., a[n]，由n个整数组成。计算将数组的所有元素拆分为三个连续部分的方法数，以便每个部分中的元素之和相同。

输入第一行包含整数n（1 ≤ n ≤ 5·10^5），显示数组中有多少个数字。第二行包含n个整数a[1]，a[2]。。。，a【n】（| a【i】| ≤  10^9）-数组a的元素。

输出打印一个整数-将数组拆分为具有相同总和的三部分的方法的数量。例如，

input
5
1 2 3 0 3
output
2

我的方法是：对所有输入的数字求和。找出它是否可以被3整除。如果不是，直接输出0，如果它可以被3整除，那么我们需要计算方法的数量。因此，我所做的是，

找到索引值（ind1，ind2，ind3），我可以找到满足给定条件的第一个子数组。也就是说，

int ind1=0,ind2=0,ind3=0;
    while (ind1 < n)
    {
        p = p + arr[ind1];
        if (p != val)
            ind1++;
        else if (p == val)
        {
            f1 = 1;
            break;
        }
    }
    ind2 = ind1;
    ind2++;
    p = 0;
    while (ind2 < n)
    {
        p = p + arr[ind2];
        if (p != val)
            ind2++;
        else if (p == val)
        {
            f2 = 1;
            break;
        }
    }
    ind3 = ind2;
    ind3++;
    p = 0;
    while (ind3 < n)
    {
        p = p + arr[ind3];
        if (p != val)
            ind3++;
        else if ( p == val )
        {
            f3 = 1;
            //ans++;
            break;
        }
    }

在我有了ind1、ind2、ind3之后，我开始检查0的存在，因为只有由于它们，我们才有不止一种方法。然而，我似乎没有从中得到正确的答案，例如，

Input: 
9
0 0 0 0 0 0 0 0 0 

正确的O/P应该是28，但我的是7。我的逻辑错了吗？

编辑：如建议：val=sum/3；//这里sum是（i=n-1； i的所有数字的总和

Answer 1

正如您已经计算出的那样，首先找到整个数组的和。你没有提到负值的可能性。所以我假设它们是可能的。

接下来，找到包含第一个元素*的每个子阵列，其和正好等于总元素的三分之一。我们将这些称为左子阵列。这应该是O（n）。你需要记录所有这些结束的地方。

现在对包含最后一个元素*的每个子数组执行相同的操作，也就是O（n），还记录它们的开始位置（因为它们显然都在同一个位置结束）。我们称之为正确的子阵列

在不透露一切的情况下，现在找出非重叠*左子数组和右子数组的组合数。（因为很明显，它们之间的子数组也有所需的总和，即总数的1/3。如果你巧妙地完成这部分，它应该是O（左子数组的数量右子数组的数量），当然，这仍然是O（n）。

我在最后一段中遗漏了一个细节，是的，但我认为对于这些类型的挑战，很高兴给您留下一点挑战。整个过程应该在O（n）中是可能的

*我应该注意到，对于这个问题，基于空子数组的和是0还是未定义，在一些细节上存在一些差异。你也需要仔细考虑这一点。（根据这个例子，我想说空子数组的和是未定义的，这意味着非重叠也需要有非0长度的间隙）

Answer 2

首先想到的是，您想找到两个拆分点，将数组绑定到恰好等于总和三分之一的子数组中：即从0到p1、p1到p2和p2到n-1。第二个是您想处理元素使您的总和超过目标值的情况。第三个是您想智能地处理数组中的零。

Answer 3

正确的O/P应该是28，但我的是7。我的逻辑错了吗？

对运行代码后，您将获得以下内容：

   ind1 ind2 ind3
    |    |    |
    0    0    0    0    0    0    0    0    0         (1)

开始搜索零后，您会发现以下配置

   ind1 ind2      ind3
    |    |         |
    0    0    0    0    0    0    0    0    0         (2)
   ind1 ind2           ind3
    |    |              |
    0    0    0    0    0    0    0    0    0         (3)
   ind1 ind2                ind3
    |    |                   |
    0    0    0    0    0    0    0    0    0         (4)
   ind1 ind2                     ind3
    |    |                        |
    0    0    0    0    0    0    0    0    0         (5)
   ind1 ind2                          ind3
    |    |                             |
    0    0    0    0    0    0    0    0    0         (6)
   ind1 ind2                               ind3
    |    |                                  |
    0    0    0    0    0    0    0    0    0         (7)

这是您找到的7种配置。但这不是您想要的。首先，您只需要两个索引，而不是3，您的ind3应该始终指向最后一个元素。您需要计算3个和——从到0到ind1-1，从到ind1到ind2，从到ind2 1到n-1。所以你需要有那个ind1

        ind1
         |
        ind2                           
         |                                 
    0    0    0    0    0    0    0    0    0         (1)

        ind1 ind2
         |    |                               
    0    0    0    0    0    0    0    0    0         (2)
        ind1      ind2
         |         |                               
    0    0    0    0    0    0    0    0    0         (3)
    ...
        ind1                          ind2
         |                             |                               
    0    0    0    0    0    0    0    0    0         (7)

然后你也应该开始移动ind1

             ind1
              |
             ind2                           
              |                                 
    0    0    0    0    0    0    0    0    0         (8)
    ...

所以你得到的配置数量是：7 6 5 ... 1= 28

还要注意，这个算法是O（n^2），由于n最多可以达到10^5，这很可能会超时。因此，为了通过所有测试，您应该使用不同的方法。您可以做的是以下事情。首先计算数组索引集A={i|a[0]a[1]... a[i-1]=sum/3}和B={i|a[i 1]a[i 2]... a[n-1]=sum/3}。您可以将A和B存储在将被排序的数组中。现在，你要找的是对的数量（i，j），使得i来自A，j来自B，使得i

9
0 0 0 0 0 0 0 0 0

A={1，2，3，4，5，6，7}和B={1，2，3，4，5，6，7}（数组从0到8）。对于A中的索引1，你有满足问题的索引{1，2，3，4，5，6，7}，对于A中的2，你有{2，3，4，5，6，7}，等等。同样，你有7 6 5 4。。。1但不是列出所有可能的索引，而是使用二进制搜索在O（log n）时间内找到它们的计数。所以总的来说，你的算法是O（n log n）。

这是moreON思想的一个实现，它进一步扩展了二进制搜索的思想。不是每次迭代都重新开始二进制搜索，而是开始搜索之前找到的索引，该索引总共产生O（n）个摊销时间

#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;

int n;
long long sum, k;
int a[500010];

void solve()
{
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%d", a + i);

    for (int i = 0; i < n; ++i)
        sum += a[i];

    if (sum % 3 != 0) {
        cout << 0 << endl;
        return;
    }
    k = sum / 3;
    vector<int> forward, backward;
    sum = 0;
    for (int i = 0; i < n-2; ++i) {
        sum += a[i];
        if (sum == k) {
            forward.push_back(i+1);
        }
    }
    sum = 0;
    for (int i = n - 1; i >= 2; i--) {
        sum += a[i];
        if (sum == k) {
            backward.push_back(i-1);
        }
    }
    reverse(backward.begin(), backward.end());

    int j = 0;
    int fn = forward.size();
    int bn = backward.size();
    long long ans = 0;
    for (int i = 0; i < fn; ++i) {
        while (j < bn && backward[j] < forward[i])
            j++;
        ans += bn-j;
    }
    cout << ans << endl;
}

int main()
{
    solve();
    return 0;
}