幂集查找子序列而不是子数组。子数组是连续的,但是子序列可以是不连续的。因此,查找数组的子序列和子数组并不相同。
根据从给定数组中查找所有可能的子数组的实现,如下所示:
public class AllPossibleSubArray {
public static void main(String[] args) {
int[] arr = { 1, 2, 3 };
List<List<Integer>> result = new ArrayList<>();
for (int len = 0; len <= arr.length; len++) {
if (len == 0) {
result.add(new ArrayList<>());
} else {
for (int i = 0; i < arr.length - len + 1; i++) {
List<Integer> temp = new ArrayList<>();
for (int j = i; j < i + len; j++) {
temp.add(arr[j]);
}
result.add(temp);
}
}
}
result.forEach(System.out::println);
}
根据我的理解,由于存在三个FOR循环,所以时间复杂度将为O(N ^ 3)。
但是这个问题只不过是一个幂集,即从给定集中找到所有可能的子集。在网络上的各种论坛上,幂集的时间复杂度为2 ^ N(二项式展开),与O(N ^ 3)不同。
我是否缺少一些基本知识?
但是这个问题只不过是一个幂集,即从给定集中找到所有可能的子集。
不正确。
您发布的代码只能找到contiguous子数组,这意味着从一个索引到另一个索引的所有元素的列表。
相比之下,幂集还将包含discontiguous子序列,这意味着它们包含两个元素,但不包括它们之间的所有元素。
我还应注意,只有O(n 2)个子数组,如果您找到其他表示它们的方式,则可以在O中找到它们(n 2)时间,而不是您发布的代码的O(n 3)时间。 (特别是,您需要一个表示形式,该表示形式允许您重复使用列表的共享部分,而不必每次都复制所有必需的元素。)相反,如果您坚持使用代码中的表示形式,其中每个列表都有一个单独的副本,找到所有子集实际上将需要O(n·2 n])时间,而不仅仅是O(2 n] >)时间。
幂集查找子序列而不是子数组。子数组是连续的,但是子序列可以是不连续的。因此,查找数组的子序列和子数组并不相同。
幂集查找子序列而不是子数组。子数组是连续的,但是子序列可以是不连续的。因此,查找数组的子序列和子数组并不相同。