Enumeration

Given an array whose elements are all distinct and none equal to $0$, find the number of pairs of numbers in the array whose sum is $0$.

The code for enumerating two numbers is easy to write.

C++

for (int i = 0; i < n; ++i)
  for (int j = 0; j < n; ++j)
    if (a[i] + a[j] == 0) ++ans;

Python

for i in range(n):
    for j in range(n):
        if a[i] + a[j] == 0:
            ans += 1

Java

for (int i = 0; i < n; ++i)
  for (int j = 0; j < n; ++j)
    if (a[i] + a[j] == 0) ++ans;

Let's see how the enumeration range can be optimized. Since the problem does not require the pairs to be ordered, the answer is twice the answer for the ordered case (consider that if (a, b) is an answer, then (b, a) is also an answer). In this case, we only need to count the answers after imposing an order, and multiply by $2$ at the end.

We may require the first number to appear later. The code is as follows:

C++

for (int i = 0; i < n; ++i)
  for (int j = 0; j < i; ++j)
    if (a[i] + a[j] == 0) ++ans;
ans *= 2;

Python

for i in range(n):
    for j in range(i):
        if a[i] + a[j] == 0:
            ans += 1
ans *= 2

Java

for (int i = 0; i < n; ++i)
    for (int j = 0; j < i; ++j)
        if (a[i] + a[j] == 0) ++ans;
ans *= 2;

It is not difficult to see that the enumeration range of $j$ has already been reduced here, reducing the time overhead of this code.

We can optimize further on this basis.

Do both numbers necessarily have to be enumerated? After enumerating one number, the conditions of the problem determine the other elements (the other number). If we can find a way to directly determine whether the required number exists, we can eliminate the time spent enumerating the latter number. More advancedly, when the data range permits, we can use a bucket¹ to record the numbers traversed.

C++

#include <cstring>
constexpr int MAXN = 100000;  // Here MAXN is the bound on elements in the array

int solve(int n, int a[]) {
  bool met[MAXN * 2 + 1];  // Create a bucket that can hold [-MAXN, MAXN]
  memset(met, 0, sizeof(met));
  int ans = 0;
  for (int i = 0; i < n; ++i) {
    if (met[MAXN - a[i]]) ++ans;  // If the desired element is in the bucket, increment the answer by one
    met[MAXN + a[i]] = true;  // In any case, put the current element into the bucket
  }
  return ans * 2;
}

Python

met = [False] * (MAXN * 2 + 1)
for i in range(n):
    if met[MAXN - a[i]]:
        ans += 1
    met[a[i] + MAXN] = True
ans *= 2

Java

boolean[] met = new boolean[MAXN * 2 + 1];
for (int i = 0; i < n; ++i) {
    if (met[MAXN - a[i]]) ++ans;
    met[MAXN + a[i]] = true;
}
ans *= 2;