查找具有指定奇数整数个数的子数组个数

Question

给定一个整数数组和一个整数m，我如何找到所有包含m个奇整数的子数组？如果我的问题不充分，下面是对整个问题的更长描述。这个问题有比n^2更快的解决方案吗？下面的解决方案似乎是n^2，我不确定如何进一步优化它。

https://github.com/cem3394/hr-haskell/blob/master/beautifulsubarrays.hs

    static long beautifulSubarrays(int[] a, int m) {
    int sum = 0;
    for (int i = 0; i < a.length; i++){
        for (int j = i, c =0; j < a.length; j++){
            if (a[j] %2 !=0){
                c++;
            }
            if ((c==m) && (z==j)){
                over = true;
                sum++;
                break
            }
            boolean over = false;
            if (over) break;
            for (int z = i, c = 0; z <= j; z++){
                if (a[z]%2 != 0){
                    c++;

                }
                if (c>m){
                    over = true;
                    break;

                }
                if ((c==m) && (z==j)){
                    over = true;
                    sum++;
                    break;
                }
            }
        }
    }
    return sum;


    }

Answer 1

这是两个指针方法的任务。

制作两个索引-L和R。

将L设为0，并将R从0向右移动，在Od计数器中计数奇数。当Od变为m时，记住R位置为r0。进一步移动R直到遇到新的奇数。

记住L的位置为L0，并递增L，直到满足奇数（如果A[L0]是奇数，则保持不变）。

现在，从L0..L范围开始，到R0..r-1范围结束的所有子数组都正好包含m个奇数。有CNT=(L-L0+1)*(R-R0)这样的子数组：

m=3 
       L0 L        R0           R
i      0  1  2  3  4  5  6  7  8 
A[i]   4  1  3  2  5  6  2  2  3

从0..1开始到4..7结束的所有子数组包含3个奇数，这里有2个索引用于start和4个索引用于end，所以cnt=8