给定一个数组找到m个奇数的子数组？

Question

样本输入:( 1 2 3 4 5数组元素) m = 1(奇数)样本输出: 8.子阵列是[ [1],[1,2],[2,3],[2,3,4],[3],[3,4],[4,5],[5]]

这是我的实现.在最坏的情况下,它需要O(n + n ^ 2).是否有任何方法来优化此代码？

int main() {
    int n, *a, count1=0, m, *dp;
    cin>>n;
    a = new int[n];
    dp =new int[n];

    for(int i=0; i<n; i++) {
        cin >> a[i];
    }

    cin >> m;

    for(int i=0; i<n; i++){
        if(a[i]%2==1) {
            count1++;
        }

        dp[i] =count1;
    }

    int prev;
    long count=0;

    for(int i=0; i<n; i++) {
        prev= i==0 ? 0:dp[i-1];
        for(int j=i; j<n; j++) {
            if((dp[j] - prev) == m){
                count++;
            }

            if(dp[j] - prev > m){
                break;
            }
        }
    }
    cout<<count;
}

Answer 1

这可以解决O(n).首先生成奇数之间的间隙长度的数组,将两端计为隐式奇数.在这种情况下,该数组是g = [0,1,1,0].然后我们求和,(g[i]+1)*(g[i+m]+1)因为它表示有多少子数组从i'奇数开始,或者在'奇数之前,或者在'奇数之后或之后i+m'开始.

在这种情况下,我们得到1*2 + 2*2 + 2*1 = 8.

替代解释 考虑所需子阵列表.每个人都从某处开始,包括m奇数,然后在其他地方结束.让我们根据它们包含的奇数字串将它们分成组.每组包含i一些奇数i,并以i+m-1'奇数号结尾.起点在第奇数i-1和i第奇数之间的每个偶数处,以及第三i个奇数本身.这是i奇数+ 1 之前的差距的大小.或者g(i)+1在我的计算中.类似地,结束点位于i+m-1第奇数,或者在i+m第奇数之间的所有平均数.这是i+m-1第一个和i+m第三个奇数之间差距的1倍.这是g(i+m)+1在我的计算中.因此,该组中的数字是起点数乘以结束点数.这是(g(i)+1)*(g(i+m)+1).在所有起点上添加,i我们有答案.

我掩饰了一个重要的细节.这是我假设包含奇数,所以0 < m.如果m = 0那时计算完全改变.答案结果证明是1 + sum(g(i)*(g(i)-1)/2).