给定一个数组，找出其中具有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;
}

- Sanjeevkumar M

---

只是作为一个有趣的点，大O符号倾向于仅使用最重要的项，因此您的算法将是O(n^2)。 - paxdiablo

Answer 1

这可以通过O(n)算法解决。首先生成一个由奇数之间的间隙长度组成的数组，将两端视为隐式奇数。在这种情况下，该数组为g = [0,1,1,0]。然后我们求和(g[i]+1)*(g[i+m]+1)，因为它表示从第i个奇数开始或刚好在第i个奇数之前，以及直到第i + m个奇数结束或刚好在第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

- btilly

---

能否请您详细解释一下？ - Akshay Mathur

@AkshayMathur 这不是需要更多的解释，而是提供其他的解释，直到有一个能够让人理解。我会再添加一个解释。 - btilly

阅读此内容以获得更多的清晰度：https://discuss.codechef.com/questions/103416/contiguous-subarray - duplex143

当i索引g中的最后一个数字时，如何获得g[i+m]？ g[i+m]将是一个不存在的元素。你是否在循环中？ - ginna

@ginna，你从哪里得到的想法，认为i是索引g中最后一个数字的位置？我只是将i用作索引变量。它从0开始，并一直持续到i+m达到数组末尾。不需要进行任何包装。 - btilly

啊，好的——我原以为变量 i 会遍历整个数组，但现在听起来好像是在结束前停止了。 - ginna

Answer 2

你可以轻松地获得O(n log n)。你的代码的一个简单改进是，在内部循环（j上），不是逐个计数，而是在区间[i，n]上进行二分搜索，以找到导致m个奇数的第一个位置和导致m + 1个奇数的第一个位置；然后相减。

但是，要做到这一点，您需要一个sum[]数组，在其中第i个位置显示区间[0，i]中奇数的数量。这可以通过一个for循环在O(n)中预先计算出来。

现在你可以像这样在二分搜索中使用它：

for(int i = 0; i < n; i++){
    int lo = i;
    int hi = n;

    while(lo < hi){
        int mid = (lo + hi)/2;
        int count = sum[mid];
        if(i > 0) count -= sum[i - 1];

        //count shows number of odd in the interval [i, mid]
        if(mid >= m){
            hi = mid;
        } 
        else{
            lo = mid + 1;
        }
    }

    int first_with_m = lo;

    //do another binary search to find first_with_m_plus_one

    answer += first_with_m_plus_one - first_with_m;
}

- A. Mashreghi