解法1——二分查找

用二分查找寻找以l为开头时，可行的最后一个r。

那么[l,r]区间的方案数为1+2+...+(r-l-1)。

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), d = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; ++i) a[i] = in.nextInt();
        final long MOD = 99997867;
        int l = 2, r = n - 1;
        long ans = 0;
        for (int i = 0; i < n - 2; ++i) {
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (a[mid] - a[i] > d) r = mid - 1;
                else l = mid;
            }
            long x = r - i - 1, s = x * (x + 1) / 2;
            ans = (ans + s) % MOD;
            r = n - 1;
        }
        System.out.println(ans);
    }
}

解法2——双指针

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), d = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; ++i) a[i] = in.nextInt();
        Arrays.sort(a);
        final long MOD = 99997867;
        long ans = 0;
        for (int l = 0, r = 0; l < n - 2; ++l) {
            while (r < n - 1 && a[r + 1] <= a[l] + d) r++;
            int x = Math.max(0, r - l - 1);
            long s = (long)x * (x + 1) / 2;
            ans = (ans + s) % MOD;
        }
        System.out.println(ans);
    }
}