javascript - 算法:我怎么不能使用滑动窗口方法来解决这个问题？

Question

我在面试的时候遇到了这个问题。它为您提供一个数组和一个阈值，该函数应返回该数组的最短、非空、连续子数组的长度，其总和至少超过该阈值。

所以如果数组是 [2,-1,2] 并且阈值是 3 那么它应该返回 3 。

这是我用 JavaScript 编写的尝试。我采用了一种典型的滑动窗口方法，一旦总和大于 threshold，我将减小窗口大小，并在每次迭代期间跟踪窗口大小。

function(array, threshold) {
  let minWindowSize = Infinity
  let sum = 0
  for (let start = 0, end = 0; end < array.length; end++) {
    sum += array[end]
    if(sum >= threshold) minWindowSize = Math.min(minWindowSize, end - start + 1)
    while (sum > threshold) {
      sum -= array[start++]
    }
  }

  return minWindowSize === Infinity ? -1 : minWindowSize
};

但是我的解决方案对于像这样的情况是错误的

array = [17,85,93,-45,-21]
threshold = 150

我想知道这个问题与典型的滑动窗口问题有什么区别，有没有办法实现滑动窗口方法来解决这个问题？看起来很简单，但结果是 be a hard question on leetcode .

Answer 1

正如 David 指出的那样，当数组中有负数时，您不能使用滑动/拉伸(stretch)窗口技术，因为总和不会随窗口大小单调增长。

不过，您仍然可以在 O(n log n) 时间内解决此问题，方法是使用通常用于“滑动窗口最小值/最大值”问题的技术。

首先，将您的数组转换为前缀和数组，方法是将每个元素替换为该元素与所有先前元素的总和。现在你的问题变成了“找到最近的差值 >= X 的元素对”(假设数组 [-1]==0)。

当你遍历数组时，你需要为每个 i 找到最新的索引 j 使得 j < i 和数组[j] <= 数组[i]-x。

为了快速做到这一点，首先要注意 array[j] 将总是小于以下所有元素，直到 i ，否则会有更接近的元素可供选择。

因此，当您遍历数组时，维护所有元素的索引堆栈，这些元素小于您后来看到的所有元素。这很容易，总体上需要 O(n) 时间——在处理完每个 i 之后，您只需弹出所有具有 >= 值的索引，然后推送 i。

然后对于每一个i，你可以在这个栈中进行二分查找，找到最新的一个值足够小的索引。二分查找有效，因为堆栈中索引的值单调递增——每个元素必须小于所有后续元素。

通过二分查找，总时间增加到 O(n log n)。

在 JavaScript 中，它看起来像这样:

var shortestSubarray = function(A, K) {
    //transform to prefix sum array
    let sum=0;
    const sums = A.map(val => {
        sum+=val;
        return sum;
    });
    const stack=[];
    let bestlen = -1;
    for(let i=0; i<A.length; ++i) {
        const targetVal = sums[i]-K;
        //binary search to find the shortest acceptable span
        //we will find the position in the stack *after* the
        //target value
        let minpos=0;
        let maxpos=stack.length;
        while(minpos < maxpos) {
            const testpos = Math.floor(minpos + (maxpos-minpos)/2);
            if (sums[stack[testpos]]<=targetVal) {
                //value is acceptable.
                minpos=testpos+1;
            } else {
                //need a smaller value - go left
                maxpos=testpos;
            }
        }
        if (minpos > 0) {
            //found a span
            const spanlen = i - stack[minpos-1];
            if (bestlen < 0 || spanlen < bestlen) {
                bestlen = spanlen;
            }
        } else if (bestlen < 0 && targetVal>=0) {
            // the whole prefix is a valid span
            bestlen = i+1;
        }
        // Add i to the stack
        while(stack.length && sums[stack[stack.length-1]] >= sums[i]) {
            stack.pop();
        }
        stack.push(i);
    }
    return bestlen;
};

Leetcode 说:

SUCCESS:

Runtime: 216 ms, faster than 100.00% of JavaScript online submissionsfor Shortest Subarray with Sum at Least K.

Memory Usage: 50.1 MB, less than 37.37% of JavaScript onlinesubmissions for Shortest Subarray with Sum at Least K.

我猜大多数人使用的是较慢的算法。