我希望找到一个算法来计算数组的不同子数组数量。
例如，在 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中，[1]来自A [0：1]和[1]来自A [2：3]不是不同的。
同样地：
B [0：1]，B [1：2]，B [2：3]也不是不同的。
构建该数组的后缀树，然后将该树中所有边的长度相加。
使用适当的算法（Ukkonen或McCreight算法），构建后缀树所需的时间为O(n)。遍历树并将长度相加所需的时间也是O(n)。
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)。
set只使用哈希，因此实际上只比较了少量序列；大多数比较都被避免了），而在于计算哈希所需的时间，其复杂度为O(n)。这应该导致此解决方案的平均复杂度为O(n^3)。 - BakuriuA[i：j]需要O(j-i)，而不是O(1)。实际上，subs的总内存使用量为O(n^3)，因此创建它所需的时间不可能更快。" - xuanji 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
如果列表中包含相同的模式，迭代和比较的次数将非常低。对于你的例子[1, 2, 1, 2]，行if (!listOfUniqueList.contains(currentList)){将执行10次。仅在包含15个不同子数组的输入[1, 2, 1, 2, 1, 2, 1, 2]中才会增加到36。
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] 元素的索引为 6。从索引 6 开始，我们可以得到两个子数组 [1] 和 [1,3]。因此，ANS = 2；
现在逐一取每个连续的对。
取 pair[0] 和 pair[1]，
pair[1] 的索引为 0。我们可以从索引 0 开始得到 8 个子数组。但是已经计算了两个子数组 [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 + 以 pair[i+1] 开头的子数组数目 - 最长公共前缀的长度。
排序部分需要 O(n logn) 时间。
迭代每个连续的一对需要 O(n)，每次迭代查找最长公共前缀需要 O(n)，整个迭代部分的时间复杂度为 O(n^2)。这是我能获得的最好结果。
您可以看到，我们不需要对此使用 pair。第一个值对于元素的值并不是必需的。我使用它只是为了更好理解。您可以随时跳过它。
我的第一个答案有点愚蠢。
我猜答案是生成所有的数组，然后删除重复项。或者如果你使用像Java这样带有set对象的语言，可以将所有的数组都添加到int[]的set中。Set只包含每个元素的一个实例，并自动删除重复项，因此您只需在最后获取set的大小即可。
我可以想到两种方法...
第一种是计算某种哈希值，然后添加到一个集合中。 如果在添加时哈希值与现有数组相同...那么进行详细比较...并记录下来，以便知道您的哈希算法不够好...
第二种是使用某种可能匹配，然后从那里深入... 如果元素数量相同且所有元素的总和相同，则进行详细检查。
[]，它是每个数组的子数组。否则，你必须将sub-array定义为非空连续序列... - Bakuriu