我想找到一个算法来计算数组的不同子数组的数量。
例如，在的情况下 A = [1,2,1,2]， 不同子阵列的数量是7：
{ [1] , [2] , [1,2] , [2,1] , [1,2,1] , [2,1,2], [1,2,1,2]}
在...的情况下 B = [1,1,1]，不同子阵列的数量是3：
{ [1] , [1,1] , [1,1,1] }
一个 子阵列 是数组的连续子序列或切片。 不同 意思是不同的内容例如：
来自A [0：1]的[1]和来自A [2：3]的[1]并不明显。
同样地：
B [0：1]，B [1：2]，B [2：3]不明显。
构造此数组的后缀树。然后在此树中添加所有边的长度。
构造后缀树所需的时间是O（n）和适当的算法（Ukkonen或McCreight的算法）。遍历树并将长度加在一起所需的时间也是O（n）。
你可以简单地制作一组子序列并计算它们，但我不确定它是最有效的方法，因为它是 O(n^2)。
在python中将是这样的：
subs = [tuple(A[i:j]) for i in range(0, len(A)) for j in range(i + 1, len(A) + 1)]
uniqSubs = set(subs)
这给你：
set([(1, 2), (1, 2, 1), (1,), (1, 2, 1, 2), (2,), (2, 1), (2, 1, 2)])
理解中的双循环清楚地表明了 O(n²) 复杂。
显然有一些关于复杂性的讨论。创建潜艇是 O(n^2) 因为有 n^2 项目。
从列表创建集合是 O(m) 哪里 m 是列表的大小， m 存在 n^2 在这种情况下，因为添加到集合中是摊销的 O(1)。
因此整体而言 O(n^2)。
编辑：我考虑如何减少迭代/比较数。 我有办法做到这一点：如果你检索一个大小为n的子数组，那么每个大小都小于n的子数组将会被添加。
这是更新的代码。
List<Integer> A = new ArrayList<Integer>();
A.add(1);
A.add(2);
A.add(1);
A.add(2);
System.out.println("global list to study: " + A);
//global list
List<List<Integer>> listOfUniqueList = new ArrayList<List<Integer>>();
// iterate on 1st position in list, start at 0
for (int initialPos=0; initialPos<A.size(); initialPos++) {
// iterate on liste size, start on full list and then decrease size
for (int currentListSize=A.size()-initialPos; currentListSize>0; currentListSize--) {
//initialize current list.
List<Integer> currentList = new ArrayList<Integer>();
// iterate on each (corresponding) int of global list
for ( int i = 0; i<currentListSize; i++) {
currentList.add(A.get(initialPos+i));
}
// insure unicity
if (!listOfUniqueList.contains(currentList)){
listOfUniqueList.add(currentList);
} else {
continue;
}
}
}
System.out.println("list retrieved: " + listOfUniqueList);
System.out.println("size of list retrieved: " + listOfUniqueList.size());
全球研究名单：[1,2,1,2]
检索到的列表：[[1,2,1,2]，[1,2,1]，[1,2]，[1]，[2,1,2]，[2,1]，[2]]
检索列表大小：7
使用包含相同patern的列表很多次迭代和比较的次数将非常少。 对于您的示例[1,2,1,2]，行if（！listOfUniqueList.contains（currentList））{执行10次。对于包含15个不同子阵列的输入[1,2,1,2,1,2,1,2]，它仅增加到36。
我的第一个答案是一个金发时刻。
我想答案是生成所有，然后删除重复。或者，如果您使用带有set对象的Java语言，请创建所有数组并将它们添加到一组int []中。集只包含每个元素的一个实例，并自动删除重复项，因此您可以在结尾处获取集的大小
我能想到两种方式......
首先是计算某种哈希然后添加到集合中。 如果添加你的哈希是相同的是一个现有的数组...然后做一个详细的比较...并记录它，以便你知道你的哈希算法不够好...
第二种是使用某种可能的匹配，然后从那里向下钻取...... 如果元素数量相同且添加在一起的元素总数相同，则请详细检查。
创建一个pair数组，其中每个对存储子数组元素及其索引的值。
pair[i] = (A[i],i);
按升序排序对 A[i] 然后降低顺序 i。
考虑例子 A = [1,3,6,3,6,3,1,3];
排序后的对数组将是 pair = [(1,6),(1,0),(3,7),(3,5),(3,3),(3,1),(6,4),(6,2)]
pair[0] 有元素的 index 6。从 index 6 我们可以有两个子阵列 [1] 和 [1,3]。所以 ANS = 2;
现在逐一取每一对。
以 pair[0] 和 pair[1]，
pair[1] 索引为0.我们可以有8个子数组 index 0。但是已经计算了两个子阵列[1]和[1,3]。因此，要删除它们，我们需要比较子数组的最长公共前缀 pair[0] 和 pair[1]。因此，从0和6开始的索引的最长公共前缀长度是2，即 [1,3]。
所以现在新的不同子阵列将是 [1,3,6] .. 至 [1,3,6,3,6,3,1,3] 即6个子阵列。
所以新的价值 ANS 是2 + 6 = 8;
因此对于 pair[i] 和 pair[i+1]
ANS = ANS + Number of sub-arrays beginning from pair[i+1] - Length of longest common prefix。
排序部分需要O（n logn）。
迭代每个连续对是O（n），并且对于每次迭代，找到最长公共前缀取O（n）使得整个迭代部分O（n ^ 2）。这是我能得到的最好的。
你可以看到我们不需要配对。对的第一个值，元素的值不是必需的。我用它来更好地理解。你总是可以跳过它。