找到数组中最长的连续体，该连续体中的值的总和等于零模 3

我编写了一段代码，用于查找数组中最长的连续体，连续体中的值之和等于零模 3，例如对于数组a[]={2,-3,5,7,-20,7}

我们有 2-3+5+7-20=-9 所以输出是 5，我的问题是复杂性，现在是O(n^3)一只鸟低声对我说，这可以在O(n)

public class mmn {
public static void main(String[] args)
{
    int a[]={2,-3,5,7,-20,7};
    int r=what(a);
    System.out.println(r);
}
private static int f(int[]a,int low, int high)
{
int res=0;
for (int i=low;i<=high;i++)
    res+=a[i];
return res;
}
    public static int what(int[]a)
    {
    int temp=0;
    for(int i=0;i<a.length;i++)
    {
        for (int j=i;j<a.length;j++)
        {
            int c=f(a,i,j);
            if (c%3==0)
            {
                if(j-i+1>temp)
                    temp=j-i+1;
            }
        }
    }
    return temp;
    }

}

尝试在 O(n) 内重写：

import java.util.*;
class Main {
public static void main (String[] args) throws Exception {
// you should use only one Scanner object
Scanner scanner = new Scanner(System.in);
int a[]={3,1,3,1,3,1};
int n=a.length;
int S[]=new int[n];
int i[]=new int[n];
int best;
int sum;

for (int j=0; j<n; j++) {
    S[j]=a[j]%3;
    i[j]=j;// initialize
    //System.out.println(S[j]);
    //System.out.println(i[j]);     
}
best=1;
for (int k=1; k<n; k++) {
    if((S[k-1]+S[k])%3==0) {//checking if we want a longer continuum
        S[k]=S[k-1]+a[k];
        i[k]=i[k-1];
    }    
    if(S[k]<S[best])//check if i should update the better
        best=k-1;
    }
    System.out.println(best);
}
}

使用动态编程计算前缀和 s[] 后，您可以迭代 s 并将其存储在索引 i 中的 s[i]%3 对的新数组中，这样第一个索引是最小索引，第二个索引是最大索引indeces，这样新数组的长度为3，然后迭代新数组并存储0,1,2的计数，最后再次迭代该数组，并找到之间的最大值
(cnt[ 3 - 模 Array[i] ].first - i,cnt[ 3 - 模 Array[i] ].second - i)。