这是一个简单的 C 版本的解决方案,它利用了 Ai + Ak must be even test:
#include <stdio.h>
static int arr[] = {9, 4, 2, 3, 6, 10, 3, 3, 10};
int main ()
{
int i, j, k;
int sz = sizeof(arr)/sizeof(arr[0]);
int count = 0;
for (i = 0; i < sz - 2; i++)
{
for (k = i + 2; k < sz; k++)
{
int ik = arr[i] + arr[k];
int ikdb2 = ik / 2;
if ((ikdb2 * 2) == ik) // if ik is even
{
for (j = i + 1; j < k; j++)
{
if (arr[j] == ikdb2)
{
count += 1;
printf("{%d, %d, %d}\n", arr[i], arr[j], arr[k]);
}
}
}
}
}
printf("Count is: %d\n", count);
}
和控制台运球:
tmp e$ cc -o triples triples.c
tmp e$ ./triples
{9, 6, 3}
{9, 6, 3}
{2, 6, 10}
{2, 6, 10}
{3, 3, 3}
Count is: 5
tmp e$
这个更复杂的版本保留了一个按值索引的 Aj 列表,从 n 立方到 n 平方(有点)。
#include <stdio.h>
#include <stdint.h>
static uint32_t arr[] = {9, 4, 2, 3, 6, 10, 3, 3, 10};
#define MAX_VALUE 100000u
#define MAX_ASIZE 30000u
static uint16_t index[MAX_VALUE+1];
static uint16_t list[MAX_ASIZE+1];
static inline void remove_from_index (int subscript)
{
list[subscript] = 0u; // it is guaranteed to be the last element
uint32_t value = arr[subscript];
if (value <= MAX_VALUE && subscript == index[value])
{
index[value] = 0u; // list now empty
}
}
static inline void add_to_index (int subscript)
{
uint32_t value = arr[subscript];
if (value <= MAX_VALUE)
{
list[subscript] = index[value]; // cons
index[value] = subscript;
}
}
int main ()
{
int i, k;
int sz = sizeof(arr)/sizeof(arr[0]);
int count = 0;
for (i = 0; i < sz - 2; i++)
{
for (k = i; k < sz; k++) remove_from_index(k);
for (k = i + 2; k < sz; k++)
{
uint32_t ik = arr[i] + arr[k];
uint32_t ikdb2 = ik / 2;
add_to_index(k-1); // A(k-1) is now a legal middle value
if ((ikdb2 * 2) == ik) // if ik is even
{
uint16_t rover = index[ikdb2];
while (rover != 0u)
{
count += 1;
printf("{%d, %d, %d}\n", arr[i], arr[rover], arr[k]);
rover = list[rover];
}
}
}
}
printf("Count is: %d\n", count);
}
和运球:
tmp e$ cc -o triples triples.c
tmp e$ ./triples
{9, 6, 3}
{9, 6, 3}
{2, 6, 10}
{2, 6, 10}
{3, 3, 3}
Count is: 5
tmp e$