c++ - 面试 - 在数组中找到偶数和对

Question

给定一个数组，如何返回总和为偶数的对数？

例如:

a[] = { 2 , -6 , 1, 3, 5 }

在这个数组中，偶数和的对数是(2,-6), (1,3) , (1,5), (3,5)

函数应返回 4，因为有 4 对，如果没有，则返回 -1。

预期时间复杂度 - O(N) 最坏情况预期空间复杂度 - O(N) 最坏情况

方法一:蛮力

Start with the first number
  Start with second number
      assign the sum to a temp variable
      check if the temp is even
          If it is increment evenPair count
      else
          increment the second index

这里的时间复杂度是O(N2)

Answer 1

int odd = 0, even = 0;
for (int i = 0; i < n; i++) {
    if (a[i] % 2 == 0) {
        even++;
    } else {
        odd++;
    }
}
int answer = (odd * (odd - 1) + even * (even - 1)) / 2;