给定一个数组，打印其和可被给定数x整除的所有可能的邻接子序列

Question

所有要求要么打印最大的数组，要么打印长度最大的数组。我想打印那些连续数组的所有组合，这些数组可以被给定的数整除。我试图解决这个问题，并想出了这个解决方案

#include<iostream>
using namespace std;

void function(int arr[], int start, int end, int div, int sum)
{
    if(start>end)
        return;
    if(!(sum%div))
    {
        if(start<end)
        {
            for(int i=start;i<=end;i++)
            {
                cout<<"  "<<arr[i];
            }
            cout<<endl;
        }
    }
    function(arr, start+1, end, div, sum-arr[start]);
    function(arr, start, end-1, div, sum-arr[end]);
}

int main()
{
    int arr[] = {2, 6, 3, 8, 5, 7, 4, 1};
    int div;
    int size = sizeof(arr)/sizeof(*arr);
    cout<<"  Enter divisor :- ";
    cin>>div;
    int sum = 0;
    for(int i=0;i<size;i++)
        sum+=arr[i];
    function(arr, 0, size-1, div, sum);

    cout<<endl;
    system("PAUSE");
    return 0;
}

这段代码非常复杂，我可以想出一个更多的解决方案，使用两个复杂度为O(n^2)的循环。我们能以n^2倍的复杂度更好地做到这一点吗？

Answer 1

我假设你已经读过答案，找到一个数组的子数组的个数，个数组的和被给定的个数除以。

如果是，那么您可以修改上述算法如下：

Input:    0  5  3  8  2  1
X = 3
Sum:   0  0  5  8 16 18 19
Mod 3: 0  0  2  2  1  0  1

所有你需要做的是打印数组每当你看到相同的值在“mod 3”输出数组。因此，在上面的例子中，您将打印索引[0]、[2]、[0,4]、[1,4]和[4,5]中的数组。

0  5  3  8  2  1
-                     0                 =  0 % 3 = 0
-------------         0 + 5 + 3 + 8 + 2 = 18 % 3 = 0
   ----------         5 + 3 + 8 + 2     = 18 % 3 = 0
      -               3                 =  3 % 3 = 0
            ----      2 + 1             =  3 % 3 = 0