找到数组中最长的连续体，连续体中的值之和等于零模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;jtemp) 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); } }
下面是Python中O(n)算法的示例，对数组进行一次传递。 该想法是dp[i][r]表示最长的序列s ，以索引i结束，其中(sum s) % 3 = r 。 我们寻找最高的dp[i][0] 。 如果前一步骤为适当的模数结果记录了任何长度，我们只能增加特定单元格的序列。 由于我们通过数组在每次迭代时只访问三个单元（常量），因此该算法具有O(n)时间和空间复杂度。 （空间可以很容易地适应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]]
在使用动态编程计算前缀sum s []之后，您可以迭代s并存储在索引i中的对s [i]％3的新数组中，使得第一个索引是最小索引，第二个索引是最大索引。 indeces，以便新数组的长度为3，然后迭代新数组并存储0,1,2的计数，最后再次迭代该数组，并找到最大值
（cnt [3 – moduloArray [i]]。first first – i，cnt [3 – moduloArray [i]] .second – i）。
为了它的乐趣：
List> 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]