如何找出一个数组的所有可能子数组？

Question

假设我有一个数组：A[] = {1,2,3}，我想找到这个数组的所有子数组。答案应该是：

{1}, {2}, {3}, {1, 2}, {2, 3}, {1, 2, 3}

{1}
{1,2}
{1,2,3}
{2}
{2,3}
{3}

如何高效地查找数组的所有可能子数组？

- rashedcs

Answer 1

数组 A 的子数组是 A[i..j]，其中 0 <= i <= j < n，n 是数组的长度。

在 C 语言中，可以像这样计算：

#include <stdio.h>

int main(){
    int A[] = {1,2,3,4,5};
    int len=sizeof(A)/sizeof(int);
    for( int i=0; i<len; i++ ){
        for( int j=i; j<len; j++ ){   // Now A[i..j] is the subarray
            for( int k=i; k<=j; k++ )
                printf("%d ", A[k]);
            printf("\n");
        }
    }
    return 0;
}

- Ankit Vallecha

---

这种方法的时间复杂度为O(n^3)。这是最高效的方法吗？我认为哈希会是一种更适合的方法，因为问题是要“高效地”找到子数组。 - Samarth Saxena

这种方法的时间复杂度是O(n)3，不是一种高效的方式。 - Shikhar Chaudhary

Answer 2

我们可以使用substr函数来查找所有可能的子数组。

代码片段：

       #include<bits/stdc++.h>
       using namespace std;


       void generateSubstring(string str)
       {
            if(str.size()==0)
            {
                return;
            }
            else
            {
                for(int i=0; i<str.size(); i++)
                {
                    for(int j=1; j<=str.size()-i; j++)
                    {
                        cout<<str.substr(i, i+j)<<endl;
                    }
                }
            }
        }


        int main()
        {
            ios::sync_with_stdio(false);
            string str;
            getline(cin, str);
            generateSubstring(str);
            return 0;
        }

- rashedcs

---

抱歉，但这个算法一点也不高效。 - Mayur Agarwal

Answer 3

一个O(n^2)的方法可能是：

for (int i = 0; i < arr.length; i++) {
    String res = "";
        for (int j = i; j < arr.length; j++) {
            res += arr[j] + " ";
                System.out.println(res);
    }
}

- Chandan Taneja

---

抱歉，但这个算法并不高效。 - Mayur Agarwal

你的解决方案不正确。它不会给出所有子数组，而只会给出其中的一个子集。 - enggPS

Answer 4

在JavaScript中

function subarray(arr){
  let sub = []
  for(let i=0;i<=arr.length-1;i++){
    for(let j=arr.length-1;j>=i;j--){
      sub.push(arr.slice(i,j+1))
    }
  }
  return sub
}

- Saksham Manocha

---

抱歉，但是这个算法一点都不高效。 - Mayur Agarwal

@MayurAgarwal，你有更好的解决方案吗？我没有看到任何可以打印所有子数组的方法，虽然递归可以实现，但时间复杂度为O(2^n)。我希望你有更好的解决方案，这也是你能够评论效率的原因。你能否请发一下？ - Bishal Jain

const subArrayList = arr => { const subArrayList = []; for(let i=0; i} - Dananjaya Gokhale

Answer 5

尝试以下代码：

def subarray(a, n) :
      for i in range(0,n):
             for j in range(i, n) :
                   for k in range(i, j+1) :
                          print(a(k), end=" ")
                   print("\n", end=" ")
a=[1, 2,3,4,5]
n=len(a)
print( all non - empty subarrays are:-)
subarray(a, n) 

- Subhodeep Chandra

---

这是一个O(n^3)的解决方案，一点也不高效。 - as8297

抱歉，但这个算法一点也不高效。 - Mayur Agarwal