java - 划分数组的方法数

Question

我想找到将数组分成 3 个连续部分的方法的数量，使得这三个部分的总和相等

-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;

}

Answer 1

就您的方法而言，它是正确的。但是有一些点可能会给 WA

1. 很可能 sum 溢出 int，因为每个元素的数量级可以达到 10^9，所以使用 long long。
2. 确保后缀和 dp 数组初始化为 0。

已经说过在这里使用 BIT 树是一种矫枉过正，因为与您的 O(nlogn) 解决方案相比，它可以在 O(n) 中完成(但确实不管你是否提交给在线法官)。对于 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) 并对照它检查你的代码，因为就您的方法而言，它是正确的，调试不适合计算器。