java - 查找具有指定数量奇数的子数组的数量

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 个开始索引和 4 个结束索引，所以 Cnt = 8
递增 L，再次记住 R0 重复此过程直到数组结束，为结果设置的每个范围添加 Cnt

指针只遍历数组一次，复杂度是线性的。