第2题

#include<iostream>
#include<algorithm>
int main()
{
    int n, d;
    std::cin >> n >> d;
    int x[n];
    for (int i = 0; i < n; ++i) {
        std::cin >> x[i];
    }
    std::sort(x, x + n);
    long long pair = 0;
    int j = 1;
    for (int i = 0; i < n; ++i) {
        while (j < n and x[j] - x[i] <= d) {
            j++;
        }
        pair += j - i - 1;
    }
    std::cout << pair << "\n";
}

该程序的时间复杂度为（ ）。

{{ select(1) }}

• $\Theta(n)$
• $\Theta(n\log n)$
• $\Theta(n^2)$
• $\Theta(n\log d)$