如何将一个数组分成多少份？

Question

我想找出将一个数组分成三个连续部分的方法数，使得这三个部分的和相等。

-10^9 <= A[i] <= 10^9

我的方法： 接收输入并检查基本情况：

for(int i=0;i<n;i++){
     a[i]= in.nextLong();
     sum+=a[i];
}
if(sum%3!=0)System.out.println("0");

如果以上方法都不行，那么可以考虑计算前缀和和后缀和。

for(int i=1;i<=n-2;i++){
        xx+=a[i-1];
        if(xx==sum/3){

            dp[i]=1;
        }        
    }

后缀和与更新二叉索引树：

for(int i=n ;i>=3;i--){
         xx+=a[i-1];
         if(xx==sum/3){
             update(i, 1, suffix);
         }
    }

现在简单地循环数组以找到总方法：

int ans=0;

for(int i=1;i<=n-2;i++){

        if(dp[i]==1)
        {

            ans+=  (query(n, suffix) - query(i+1, suffix)); 
         // Checking For the Sum/3 in array where index>i+1
        }
}

我使用上述方法得到了错误的答案。

我不知道哪里出错了，请帮助我纠正错误。

更新和查询功能：

public static void update(int i , int value , int[] arr){

       while(i<arr.length){
           arr[i]+=value;

           i+=i&-i;

       }
}
public static int query(int i ,int[] arr){

     int ans=0;

       while(i>0){

           ans+=arr[i];
           i-=i&-i;
       }

       return ans;

}

- user4447943

---

在查询函数中，你写了 arr+=ss[i]，但是 arr 是一个数组？难道不应该是 ans+=arr[i] 吗？ - advocateofnone

@sasha 对不起，这是我的编辑错误！！！ - user4447943

你能准确地告诉我它在哪个输入处出错了吗？ - advocateofnone

我不知道测试用例是否隐藏了样例输入，例如 3 0 3 0 3 是否给出了正确答案。 - user4447943

@Codor我的else代码会给我一个答案0，我已经测试了你提供给我的输入，它给出了正确的答案。 - user4447943

Answer 1

就您的方法而言，是正确的。但是有些点可能会导致 WA:

1. 由于每个元素的幅度可以为 10^9，所以很可能 sum 溢出 int，请使用 long long。
2. 确保后缀和 dp 数组初始化为 0。

话虽如此，在这里使用 BIT 树有些过度设计，因为它可以通过 O(n) 的解决方案完成，与您的 O(nlogn) 解决方案相比（但如果您将其提交到在线评测机，则不重要）。 对于 O(n) 方法，只需获取您的 suffix[] 数组。并且像您一样标记 suffix[i]=1，如果从 i 到 n 的总和为 sum/3，则可以向后遍历该数组，并在 O(n) 的情况下完成此操作。 然后再次从后向前遍历执行 suffix[i]+=suffix[i-1]（除基本情况外 i=n）。现在，suffix[i] 存储了索引 i<=j<=n 的数量，使得从索引 j 到 n 的总和为 sum/3，这就是您试图使用 BIT 实现的内容。
因此，我建议编写一个暴力或该简单的 O(n) 方法，并对其进行检查， 因为就您的方法而言，它是正确的，而调试并不适合 stackoverflow。

- advocateofnone

---

理想情况下应该是 i 而不是 i+1。 - advocateofnone

为什么计算总和时，需要将数组从 0 到 i、从 i+1 的单独元素和从 i+2 到 n 的部分分成三个部分？这样做的目的是计算从 i+2 到 n 的部分的总和。 - user4447943

是的，你也正确地指出了你正在使用基于 BIT 1 的索引，而你的数组是基于 0 的索引。 - advocateofnone

是的，但如果1到i是一个部分，i+1到n将永远不会是另一个部分，因为这意味着sum(1到i)+sum(i+1,n)是总和，这是不可能的，因为它们都是totalsum/3，所以无论你选择i还是i+1都没有关系。 - advocateofnone

让我们在聊天中继续这个讨论：http://chat.stackoverflow.com/rooms/68797/discussion-between-sasha-and-user4447943。 - advocateofnone

Answer 2

首先，我们计算一个数组dp，其中dp[i] = 从0到i的总和，这可以在O(n)时间内完成。

long[]dp = new long[n];
for(int i = 0; i < n; i++)
   dp[i] = a[i];
   if(i > 0)
     dp[i] += dp[i - 1];

其次，假设数组的总和为x，则需要找到dp[i] == x/3的位置；对于每个dp[i] == 2*x/3的位置，我们需要将小于i的索引j的数量加入最终结果，其中dp[j] == x/3。保留html标签。

int count = 0;
int result = 0;
for(int i = 0; i < n - 1; i++){
    if(dp[i] == x/3)
       count++;
    else if(dp[i] == x*2/3)
       result += count;
}

答案在result中。

你的方法有什么问题是，

    if(dp[i]==1)
    {

        ans+=  (query(n, suffix) - query(i+1, suffix)); 
     // Checking For the Sum/3 in array where index>i+1
    }

这是错误的，应该是

(query(n, suffix) - query(i, suffix));

因为我们只需要删除从1到i，而不是从1到i+1的部分。

不仅如此，这一部分：

for(int i=1;i<=n-2;i++){
  //....      
}

第一部分：

应该是 i <= n - 1;

同样地，这部分，for(int i=n ;i>=3;i--)，应该是 i >= 1

for(int i=0;i<n;i++){
     a[i]= in.nextLong();
     sum+=a[i];
}

应该是

。

for(int i=1;i<=n;i++){
     a[i]= in.nextLong();
     sum+=a[i];
}

你的代码中有很多小错误，你需要花费很多精力来调试，直接在这里提问并不是一个好主意。

- Pham Trung

---

无法理解您的问题，如果某个位置 i 的前缀和为 sum/3，则在位置 i+2 到 n 处检查后缀和等于 sum/3 的数量，中间部分必须满足和等于 sum/3。 - user4447943

@user4447943 修复那个问题，但是有一件事情是在初始化部分，你从0开始索引 for(int i=0;i<n;i++)，但之后所有的索引都从1开始，这样正确吗？ - Pham Trung

Answer 3

在所提出的问题中，我们需要找到一个数组中三个连续部分的和相同。我将提供解决该问题的步骤以及代码片段。

1. 通过线性扫描O(n)获取数组的总和，并计算出sum/3。
2. 从末尾开始扫描给定的数组。在每个索引处，我们需要存储可以得到与(sum/3)相等的和的方式数量，即如果end[i]为3，则从索引i到n(数组范围)开始的数组中有3个子集的和为sum/3。
3. 第三步是从开头开始扫描并找到和为sum/3的索引。在找到索引后，将end[i+2]添加到解决方案变量(初始化为零)中。

这里我们要做的是从开头开始遍历数组直到len(array)-3。在找到和为sum/3的情况下，例如在索引i上，我们就有了我们需要的前半部分。

现在，不用关心后半部分，将end[i+2]的值加到解决方案变量（初始为零）中。 end[i+2]告诉我们从i+2开始到结束的总共方法数，以使第三部分的总和等于sum/3。

这里，我们已经处理了第一部分和第三部分，通过这样做，我们也已经处理了第二部分，第二部分默认等于sum/3。我们的解决方案变量将是问题的最终答案。

以下是代码片段，以更好地理解上述算法：-

在此，我们进行向后扫描，以存储从每个索引到结束的方式数，以获得sum/3。

long long int *end = (long long int *)calloc(numbers, sizeof(long long int);
long long int temp = array[numbers-1];
if(temp==sum/3){
    end[numbers-1] = 1;
}
for(i=numbers-2;i>=0;i--){
    end[i] = end[i+1];
    temp += array[i];
    if(temp==sum/3){
        end[i]++;
    }
}

一旦我们拥有了最终数组，我们执行正向循环并得到我们的最终解决方案。

long long int solution = 0;
temp = 0;
for(i=0;i<numbers-2;i++){
    temp+= array[i];
    if(temp==sum/3){
        solution+=end[i+2];
    }
}

solution 存储最终答案，即将数组分成三个连续部分并且每个部分的和相等的方案数。

- smutneja03