複雜度 O(n^2)。記得要檢查 Array Boundary。
Complexity O(n^2). Remember to check array boundaries.
UVa Link
#include <cstdio>
#include <algorithm>
int in[5000];
int main() {
int n;
while (scanf("%d", &n) != -1) {
for (int i = 0; i < n; i++) scanf("%d", &in[i]);
std::sort(in, in + n);
unsigned long long ans = 0;
for (int xi = 0; xi < n - 2; xi++) {
int yi = xi + 1, zi = xi + 2;
while (yi < n - 1 && zi < n) {
if (in[xi] + in[yi] > in[zi]) zi++;
else if (in[xi] + in[yi] < in[zi]) yi++;
else {
int ycnt = 1, zcnt = 1;
while (in[xi] + in[++yi] == in[zi] && yi < n - 1) ycnt++;
while (in[xi] + in[yi-1] == in[++zi] && zi < n) zcnt++;
ans += ycnt * zcnt;
}
}
}
printf("%llu\n", ans);
}
}