算法 y总给的思路 滑窗 $O(n)$

根据题意可知 三元组的最大元素和最小元素之差为d，可以将所有元素放到一个数组里。
维护一个窗口大小为d的窗口，每次答案增加 窗口中属于a的个数*属于b的个数*属于c的个数
需要注意在窗口滑动过程中会出现重复计算，例如第一次窗口为[0,6] 第二次窗口为[3,7]，那么[3,6]这段会被重复计算，需要减去。
代码写的不够简洁，献丑了。

java 代码

import java.util.*;
class Main{
    static class Pos{
        int val;
        int id;
        Pos(int a,int b){
            val = a;
            id = b;
        }
    }
    static int[][] cnt;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int l1 = sc.nextInt();
        int l2 = sc.nextInt();
        int l3 = sc.nextInt();
        int d = sc.nextInt();
        int[] a = new int[l1];
        int[] b = new int[l2];
        int[] c = new int[l3];
        for(int i=0;i<l1;i++)a[i] = sc.nextInt();
        for(int i=0;i<l2;i++)b[i] = sc.nextInt();
        for(int i=0;i<l3;i++)c[i] = sc.nextInt();
        ArrayList<Pos> list = new ArrayList<>();
        for(int i:a) list.add(new Pos(i,0));
        for(int i:b) list.add(new Pos(i,1));
        for(int i:c) list.add(new Pos(i,2));
        Collections.sort(list,(p1,p2)->p1.val-p2.val);
        int l=0;
        long res = 0;
        int n = list.size();
        cnt = new int[n+1][3];
        for(int i=1;i<=n;i++){
            for(int j=0;j<3;j++)cnt[i] = cnt[i-1].clone(); 
            cnt[i][list.get(i-1).id]++;
        } 
        for(int i=1;i<list.size();i++){
            Pos p = list.get(i);
            if(list.get(l).val+d<p.val){
                //window size too large
                long t1 = cnt[i][0]-cnt[l][0];
                long t2 = cnt[i][1]-cnt[l][1];
                long t3 = cnt[i][2]-cnt[l][2];
                res += t1*t2*t3;
                while(list.get(l).val+d<list.get(i).val) l++;
                if(l!=i){
                    t1 = cnt[i][0]-cnt[l][0];
                    t2 = cnt[i][1]-cnt[l][1];
                    t3 = cnt[i][2]-cnt[l][2];  
                    res -= t1*t2*t3;                 
                }
            }
        }
        long t1 = cnt[n][0]-cnt[l][0];
        long t2 = cnt[n][1]-cnt[l][1];
        long t3 = cnt[n][2]-cnt[l][2];
        res += t1*t2*t3;        
        System.out.print(res);
        return;
    }
}