Here’s a linear-time algorithm.

First observe that, for fixed i, as j increases, max - min cannot decrease. If it exceeds K, we can exit the inner loop early. Also, we can make the outer loop downward if we like.

public static long process(List<Integer> list, int K) {
  long result = 0;
  for (int i = n - 1; i > -1; i--) {
    int max = list.get(i), min = list.get(i);
    int j;
    for (j = i; j < n; j++) {
      int p = list.get(j);
      max = Math.max(max, p);
      min = Math.min(min, p);
      if (max - min > K)
        break;
    }
    result += j - i;
  }
  return result;
}

These changes allow us to achieve an output-sensitive running time of O(n + answer), but of course the answer can still be quadratic.

The final idea, getting us to O(n), is that, as i decreases, the j on which the inner loop exits cannot increase. If we could iterate j down instead of up, then each subsequent loop could pick up where the previous one stopped. This requires data structure support: a queue that supports push/pop/min/max each in amortized constant time.

The overall algorithm iterates downward over i. In each iteration, it pushes the element at index i into the queue; then, until the queue has max - min <= K, pops from the queue, and finishes the iteration by adding the number of sub-arrays starting at i (= the length of the queue).

Following solution uses the Java 8 streams API, not sure if that helps in your context.

• Step 1: Idea is to represent each subarray as Entry Class, identify all possible subarrays (Using flatMap).
• Step 2: Apply distinct to remove any duplicate subarrays (had to override hashcode and equals methods in Entry class).
• Step 3: Filter the subarray by using eligibleEntry method.

    public static long process(List<Integer> list, int k) {
        return IntStream.range(0,list.size()).boxed()
                .flatMap(index ->
                        IntStream.range(0,list.size())
                                .mapToObj(innerIndex -> new Entry(index, innerIndex)))
                .distinct()
                .filter(entry -> eligibleEntry(entry, list, k))
                .count();
    }

    private static boolean eligibleEntry(Entry entry, List<Integer> list, int k) {
        int start = entry.startIndex < entry.endIndex ? entry.startIndex : entry.endIndex;
        int end = entry.startIndex < entry.endIndex ? entry.endIndex : entry.startIndex;
        IntSummaryStatistics stats = IntStream.range(start, end + 1).mapToObj(list::get).collect(Collectors.summarizingInt(Integer::intValue));
        return (stats.getMax() - stats.getMin()) <= k;
    }

    private static class Entry {
        Integer startIndex;
        Integer endIndex;

        public Entry(Integer startIndex, Integer endIndex) {
            this.startIndex = startIndex;
            this.endIndex = endIndex;
        }

        @Override
        public boolean equals(Object other) {
            if (this == other) return true;
            if (other == null || getClass() != other.getClass()) return false;
            Entry entry = (Entry) other;
            return (startIndex.equals(entry.startIndex) && endIndex.equals(entry.endIndex)) ||
                    (startIndex.equals(entry.endIndex) && endIndex.equals(entry.startIndex));
        }

        @Override
        public int hashCode() {
            return Objects.hash(startIndex + endIndex);
        }

        @Override
        public String toString() {
            return "{" + startIndex +
                    ", " + endIndex + "}";
        }
    }

I can outline an answer in Python that behaves as O(n) up to 5 lakh (2**19) whether there are many repeated elements in the array or not -- I based this on the observation that the time needed to run each seuccessively larger array takes approx twice as long.

Assuming there are repeats in the array, it makes sense to store the unique sorted elements, v, and their tally, m: if there are 10 1s and 5 2s the 50 pairs of 1 and 2 don't need to be processed more than once.

Now, starting at i=0 and j=1 see if v[1] - v[0] <= K. If it is, compute the count and increment j. If the new difference is still in range, update the count for pairs between v[0] and v[2] and v[1] and v[2]. If incrementing j gives a difference that is too large, increase i until the difference is in range; if incrementing j is not valid then you are done. In Python, it looks like this:

def subcount(arr, K):
    # get unique values and their count/tally
    v = {}
    for i, j in enumerate(arr):
        if j not in v:
            v[j] = 0
        v[j] += 1
    v, m = zip(*[(vi, v[vi]) for vi in sorted(v)])
    # initialize
    n = 0
    i = 0
    j = 1
    N = len(v)
    while i < N:
        vi = v[i]
        while True:
            if j < N and v[j] - vi <= K:
                # count new valid pairs
                for _ in range(i, j):
                    n += m[_]*m[j]
                j += 1
            else:
                if j >= N:
                    i = j
                    break  # done
                while v[j] - v[i] > K:
                    # move i to give valid diff
                    i += 1
                break
    # self and singleton counts
    for i in range(N):
        # self pairs
        n += m[i]*(m[i] - 1)//2
        if v[i] <= K:
            # self singletons
            n += m[i]
    return n

>>> a = [1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4,
4, 4, 4, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8,
8, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 11, 11, 11, 11, 12, 12, 12,
13, 13, 13, 13, 14, 14, 14, 15, 15, 15, 16, 16, 16, 16, 16, 16,
16, 16, 16, 17, 17, 18, 18, 18, 18, 19, 19, 19, 19, 19, 19, 20, 20, 20, 20, 20]
>>> subcount(a, 4)
2022
>>> subcount(a[:20]+a[-20:],4)  # first and last row of a as shown above
400

This is an O(n) Java implementation of David Eisenstat's idea in another answer. The QueueWithMinMax data structure I use is taken from the QueueWithMax data structure by Shivam in this post, except I added functionality for tracking minimums as well.

Here's the full program (I'm iterating by increasing i instead of the originally suggested decreasing i, but this has no consequence).

public static long process(List<Integer> list, int k) {
    long result = 0;
    var min_max_queue = new QueueWithMinMax<Integer>();
    for (int i = 0; i < list.size(); i++) {
        int x = list.get(i);
        min_max_queue.offer(x);
        while (min_max_queue.getMax() - min_max_queue.getMin() > k)
            min_max_queue.poll();
        result += min_max_queue.size();
    }
    return result;

The QueueWithMinMax class:

public class QueueWithMinMax<T extends Comparable<T>> {
    Queue<T> queue;
    Deque<T> cMax; // candidates for Max value
    Deque<T> cMin; // candidates for Min value

    public QueueWithMinMax() {
        queue = new LinkedList<>();
        cMax = new LinkedList<>();
        cMin = new LinkedList<>();
    }

    public void offer(T element) {
        queue.offer(element);
        while (!cMax.isEmpty() && element.compareTo(cMax.peekLast()) > 0) {
            cMax.pollLast();
        }
        while (!cMin.isEmpty() && element.compareTo(cMin.peekLast()) < 0) {
            cMin.pollLast();
        }
        
        cMax.offerLast(element);
        cMin.offerLast(element);
    }

    public T poll() {
        if (cMax.peekFirst().equals(queue.peek()))
            cMax.pollFirst();
        if (cMin.peekFirst().equals(queue.peek()))
            cMin.pollFirst();
        return queue.poll();
    }

    public T getMax() {
        return cMax.peekFirst();
    }
    public T getMin() {
        return cMin.peekFirst();
    }
    public int size() {
        return queue.size();
    }
}

Example usage:

System.out.println(process(Arrays.asList(1, 3, 6), 3)); // 5

System.out.println(process(Arrays.asList(16, 5, 10, 14), 5)); // 6

System.out.println(process(Arrays.asList(19, 3, 13, 4, 7, 3, 18), 7)); // 10