arrays - 算法:奇偶数数组

Question

给定一个包含 n 个元素的数组，我想计算其中奇数和偶数一样多的数组的最大范围。

例子

输入:

2 4 1 6 3 0 8 10 4 1 1 4 5 3 6

预期输出:

12

我尝试了什么

我尝试使用以下步骤:

• 将所有奇数变为1，将所有偶数变为-1
• 检查所有可能的子数组，并为每个子数组计算 1 和 -1 值的总和。
• 取这些子数组中最大的和为0的子数组

但这具有 O(n^2) 的时间复杂度。

问题

如何在 O(n) 中完成此操作？

Answer 1

给定:数组a

任务:找到奇数和偶数个数都为偶数的最大子数组

解 O(n)

1. 在 java 中，当用 -1 替换奇数，用 1 替换偶数时，为每个累积和创建一个具有最高条目的 HashMap m:

   Map<Integer, Integer> m = new HashMap<>();
   int sum = 0;
   for (int i = 0; i < a.length; i++) {
     sum += a[i] % 2 == 0 ? 1 : -1;
     m.put(sum, i);
   }
   

2. 在 java 中使用 m 寻找最大距离，找到总和为 0 的最大子数组:

   int bestStart = -1, bestEnd = -1; // indexes, so end inclusive
   sum = 0;
   for (int i = 0; i < a.length; i++) {
     Integer end = m.get(sum);
     sum += a[i] % 2 == 0 ? 1 : -1;
     if (end != null && end - i > bestEnd - bestStart) {
       bestStart = i;
       bestEnd = end;
     }
   }
   

它基于您可以使用 cumSum[y] - cumSum[x - 1] 获得从 x 到 y 的总和(在将元素转换为 1 和 -1 之后)。因此，如果我们希望它为 0，则它们需要相同(注意如果 x = 0 则 cumSum = 0，cumSum[-1] 未定义)。