假设我有一个数组:A[] = {1,2,3}
,我想找到这个数组的所有子数组。答案应该是:
{1}, {2}, {3}, {1, 2}, {2, 3}, {1, 2, 3}
{1}
{1,2}
{1,2,3}
{2}
{2,3}
{3}
如何高效地查找数组的所有可能子数组?
假设我有一个数组:A[] = {1,2,3}
,我想找到这个数组的所有子数组。答案应该是:
{1}, {2}, {3}, {1, 2}, {2, 3}, {1, 2, 3}
{1}
{1,2}
{1,2,3}
{2}
{2,3}
{3}
数组 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;
}
#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;
}
一个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);
}
}
在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
}
for(let i=0; i}
- Dananjaya Gokhaledef 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)