找到陣列中最長的連續區，連續區的值之和等於零模3

Question

我寫了一個代碼，它可以找出數組中最長的連續區，即連續區中的值之和等於零的模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); 
} 
} 

Answer 1

下面是在Python一個O(n)算法的圖示，使得一個通在陣列上。想法是dp[i][r]代表最長的序列，s，結束於索引i，其中(sum s) % 3 = r。 Cleary我們尋找最高的dp[i][0]。如果前一步記錄了適當的模數結果的任何長度，我們只能增加特定單元格的序列。由於在每次迭代中我們只訪問三個單元（一個常量），所以該算法具有時間和空間的複雜性。 （空間可以很容易地適應O(1)，因爲我們只需要前三個單元在每次迭代）

a = [2,-3,5,7,-20,7] 

best = 0 
bestIndex = -1 

dp = [[0,0,0] for i in range(len(a) + 1)] 

for i in range(1,len(a) + 1): 
    r = a[i-1] % 3 

    for j in range(3): 
    canSumToJ = dp[i-1][(3 + j - r) % 3] > 0 

    dp[i][j] = max(1 if r == j else 0 
        ,1 + dp[i-1][(3 + j - r) % 3] if canSumToJ else 0) 

    bestIndex = i - 1 if dp[i][0] > best else bestIndex 
    best = max(best,dp[i][0]) 

print(best,(bestIndex - best + 1, bestIndex)) # (5, (0, 4)) 

# dp 
# => [[0, 0, 0] 
# ,[0, 0, 1] 
# ,[1, 0, 2] 
# ,[0, 3, 2] 
# ,[3, 1, 4] 
# ,[5, 4, 2] 
# ,[3, 6, 5]] 

Answer 2

在索引i，使得計算前綴和S []使用動態編程，則可以遍歷S和存儲在一對S [I]％3的新數組後第一個索引是最小索引，第二個索引是最大索引，所以新數組的長度爲3，然後迭代新數組並存儲0,1,2的計數，最後再次迭代該數組，最後找到
之間的最大值（cnt [3 - moduloArray [i]] .first - i，cnt [3 - moduloArray [i]] .second - i）。

Answer 3

對於它的樂趣：

List<List<Integer>> list = IntStream.range(0, arrayLenght).mapToObj(x -> x) 
      .flatMap(i -> IntStream.range(i, arrayLenght) 
        .mapToObj(j -> Arrays.stream(array).skip(i).limit(arrayLenght - j).mapToObj(t -> t) 
          .collect(Collectors.toList()))) 
      .collect(Collectors.toList()); 

int result = list.stream().filter(l -> l.stream().collect(Collectors.summingInt(u -> u)) % 3 == 0) 
      .max(Comparator.comparing(List::size)) 
      .map(List::size) 
      .orElse(-1); 

它大概可以改善甚至進一步用少一點的操作。

但至少會像輸入工作：

[1,3,3,3,1]