采访 - 在数组中查找偶数和对

Question

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

例如:

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

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

函数应返回4,因为有4对或-1,如果没有.

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

方法1:蛮力

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;