有效的方法，以找到所有这样的三重奏(从给定的一组数字)的数字是在A.P.？

Question

可能重复： fastest algorithm count number of 3 length AP in array

我一直在研究从CodeChef的Nov12挑战中获取的以下问题。我尝试使用基本公式来检查三个数字a，b，c是否在A.P.中，如果c-b=b-a，即2b=a+c，下面是问题：

输入的第一行包含整数N (3≤N≤100000)。然后，下一行包含N个分隔整数A1、A2、…，它们的值在1到30000之间(包括在内)。

输出选择三元组的方法的数量，使它们是算术级数的三个连续项。示例

输入：

10

3 5 3 6 3 4 10 4 5 2

产出:9

解释：

以下是选择三胞胎的所有9种方法

1：(i，j，k) = (1，3，5)，(Ai，Aj，Ak) = (3，3，3)

2：(i，j，k) = (1，6，9)，(Ai，Aj，Ak) = (3，4，5)

3：(i，j，k) = (1，8，9)，(Ai，Aj，Ak) = (3，4，5)

4：(i，j，k) = (3，6，9)，(Ai，Aj，Ak) = (3，4，5)

5：(i，j，k) = (3，8，9)，(Ai，Aj，Ak) = (3，4，5)

6：(i，j，k) = (4，6，10)，(Ai，Aj，Ak) = (6，4，2)

7：(i，j，k) = (4，8，10)，(Ai，Aj，Ak) = (6，4，2)

8：(i，j，k) = (5，6，9)，(Ai，Aj，Ak) = (3，4，5)

我使用的代码是

#include<stdio.h>
int scan() {
    int p=0;
    char c;
    c=getchar_unlocked();
    while(c<'0' || c>'9')
        c=getchar_unlocked();
    while(c>='0' && c<='9'){
        p=(p<<3)+(p<<1)+c-'0';
        c=getchar_unlocked();
    }
    return(p);
}
int main() {
    int N, i, j, k, count=0;
    N=scan();
    int a[N];
    for(i=0;i<N;i++)
        a[i]=scan();
    for(i=0;i<N-2;i++)
        for(j=i+1;j<N-1;j++)
            for(k=j+1;k<N;k++)
                if(a[k]+a[i]==2*a[j])
                    ++count;
    printf("%d\n", count);
    return 0;
 }

正如您可以看到对变量的约束，很明显，我们需要快速和有效的阿尔戈。为了安全起见，我甚至使用了更快的I/O，但程序仍然没有时间。很明显，该算法没有那么有效，因为我使用了三个嵌套循环。另一种减少某些k的数量的方法是在找到匹配时立即中断k‘循环，然后我会添加一个继续；在++count下面，这是工作的，但同样没有问题所要求的那么有效。

请告诉我一些快速的方法来做这件事，或者我是否可以在这里学习一些数学定理来更快地找到AP三胞胎。

Answer 1

我不认为你需要数组。

从方程2b=a+c中求解b，结果是：

b = (a + c) / 2

使用4个变量：a, b, c, and counter。

1. 通过读取3个值初始化a, b, c。
2. 如果(a+c)/2 == b，增量计数器，并打印a、b、c。
3. 移位变量:a= b，b= c。
4. 而cin >> c则：
5. 如果(a+c)/2 == b，增量计数器并打印a、b、c。
6. 移位变量:a= b，b= c；
7. 结束的时候。
8. 计数器的输出值

在我看来很有效率。