c++ - 如何让我的关于“算术子串”的代码更快地工作

Question

我的课程代码有一些问题。即使它工作正常，我也没有时间完成一半的示例。这是任务（我真的尽力翻译它）：

对于某些 n，您有数字 1,2,...,n 的排列。所有连续的排列数一起创建序列 a1、a2、an。你的任务是计算一个长度为 3 的序列有多少算术子串存在。

输入：第一行有一个数字 n (1 <= n <= 200 000)。第二行有 n 个数字 a1, a2...an 代表我们的排列。

输出：程序需要打印出长度为 3 的算术子串的数量，以便从条目中进行排列。您可以假设结果不会大于 1 000 000。

有没有办法让它更快地工作？感谢帮助！

#include <iostream>
using namespace std;

int main() 
{
    int input_length;
    cin >> input_length;
    int correct_sequences = 0;
    
    bool* whether_itroduced = new bool[input_length + 1]{0}; // true - if number was already introduced and false otherwise.
    
    
    for (int i = 0; i < input_length; i++)
    {
        int a;
        cin >> a;
        whether_itroduced[a] = true;
        int range = min(input_length - a, a - 1); // max or min number that may be in the subsequence e.g. if introduced number a = 3, and all numbers are six, max range is 2 (3 - 2 = 1 and 3 + 2 = 5, so the longest possible subsequence is 1, 3, 5)
        
        for (int r = range * -1; r <= range; r++) // r - there is a formula used to count arithmetic sequences -> an-1 = a1-r, an = a1, an+1 = a1+r, I have no idea how to explain it
        {
            if (r == 0) continue; // r cannot be 0
            
            if (whether_itroduced[a - r] && !whether_itroduced[a + r])
            correct_sequences++;
            
        }
    }
    cout << correct_sequences;
}

示例输入：5 1 5 4 2 3 输出：2 // 1,2,3 和 5,4,3

标签： c++