性质：(l, r)是连续区间，记区间max，min，则有max - min == r - l

即(l, r)区间共有n个数字，n = max - min + 1
max - min表示(l, r)区间的数值落在数值的范围，由于数组的数值各个不同
那么区间中数量只能为max - min + 1个才可以填满max到min的每一个整数

就有等式max - min + 1 == r - l + 1
即为max - min == r - l

import java.util.*;

public class Main {
    static final int N = 10010;
    static int[] a = new int[N];
    static int n;

    public static void main(String[] args) {

        Scanner sc=  new Scanner(System.in);

        n = sc.nextInt();
        sc.nextLine();

        String[] s = sc.nextLine().split(" ");
        for (int i = 0; i < n; i++) a[i] = Integer.parseInt(s[i]);

        int res = 0;
        for (int i = 0; i < n; i++) {
            int max = -N, min = N;
            for (int j = i; j < n; j++) {
                max = Math.max(max, a[j]);
                min = Math.min(min, a[j]);
                if (max - min == j - i) res++;
            }
        }

        System.out.println(res);
    }
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla