O (n) решение для подсчета массивов с суммами ограничений

Question

Я пытаюсь улучшить свою интуицию в отношении следующих двух проблем подмассива.

Проблема первая

Return the length of the shortest, non-empty, contiguous sub-array of A with sum at least 
K. If there is no non-empty sub-array with sum at least K, return -1

Я наткнулся на O(N) решение онлайн.

public int shortestSubarray(int[] A, int K) {
    int N = A.length;
    long[] P = new long[N+1];
    for (int i = 0; i < N; ++i)
        P[i+1] = P[i] + (long) A[i];

    // Want smallest y-x with P[y] - P[x] >= K
    int ans = N+1; // N+1 is impossible
    Deque<Integer> monoq = new LinkedList(); //opt(y) candidates, as indices of P

    for (int y = 0; y < P.length; ++y) {
        // Want opt(y) = largest x with P[x] <= P[y] - K;
        while (!monoq.isEmpty() && P[y] <= P[monoq.getLast()])
            monoq.removeLast();
        while (!monoq.isEmpty() && P[y] >= P[monoq.getFirst()] + K)
            ans = Math.min(ans, y - monoq.removeFirst());

        monoq.addLast(y);
    }

    return ans < N+1 ? ans : -1;
}

Похоже на поддержание раздвижного окна с настилом. Это похоже на вариант алгоритма Кадане.

Задача два

Given an array of N integers (positive and negative), find the number of 
contiguous sub array whose sum is greater or equal to K (also, positive or 
negative)"

Лучшее решение, которое я видел, это O(nlogn), как описано вследующий ответ .

tree = an empty search tree
result = 0
// This sum corresponds to an empty prefix.
prefixSum = 0
tree.add(prefixSum) 
// Iterate over the input array from left to right.
for elem <- array:
    prefixSum += elem
    // Add the number of subarrays that have this element as the last one
    // and their sum is not less than K.
    result += tree.getNumberOfLessOrEqual(prefixSum - K) 
    // Add the current prefix sum the tree.
    tree.add(prefixSum)
print result

Мои вопросы

1. Моя интуиция, что первый алгоритм является вариантом алгоритма Канданаправильно?

2. Если так, есть ли вариант этого алгоритма (или другое решение O(n)), который можно использовать для решения второй проблемы?

3. Почему проблему два можно решить только в O(nlogn) время, когда они выглядят так похоже?