我在面试时遇到了这个问题。它为您提供一个数组和一个阈值,该函数应返回该数组的最短、非空、连续子数组的长度,其总和至少超过该阈值。
因此,如果数组是
[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
我想知道这个问题与典型的滑动窗口问题有什么区别,有没有办法实现滑动窗口方法来解决这个问题?这看起来很简单,但事实证明这是 leetcode 上的一个难题。
不过,您仍然可以在 O(n log n) 时间内解决这个问题,使用通常用于“滑动窗口最小值/最大值”问题的技术。
首先,将数组转换为前缀和数组,方法是将每个元素替换为该元素与所有先前元素的总和。 现在你的问题变成了“找到最接近的一对差异 >= X 的元素”(假设 array[-1]==0)。
当您迭代数组时,您需要为每个
i找到最新索引 j,使得 j 和 array[j] < i. <= array[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 说:
成功:
运行时间:216 ms,比 100.00% 的 JavaScript 在线提交快 对于总和至少为 K 的最短子数组。
内存使用量:50.1 MB,低于在线 JavaScript 的 37.37% 提交总和至少为 K 的最短子数组。
我猜大多数人都使用较慢的算法。
我不知道如何用滑动窗口解决这个问题。我想到的方法是循环前缀和,在搜索线段树中查找至少
threshold
小的最新总和后,将每个前缀和插入到线段树中。
通过使用双端队列,我们可以以一种允许我们维护子数组之和至少为 k 的窗口的方式跟踪元素的索引。该解决方案使用前缀和,通过减去两个前缀和来帮助有效计算任何子数组的和。
function shortestSubarray(nums, k) {
const n = nums.length;
let prefixSum = Array(n + 1).fill(0);
// Compute prefix sums
for (let i = 0; i < n; i++) {
prefixSum[i + 1] = prefixSum[i] + nums[i];
}
let deque = [];
let minLength = Infinity;
for (let i = 0; i <= n; i++) {
// Try to find the smallest subarray with sum >= k
while (deque.length > 0 && prefixSum[i] - prefixSum[deque[0]] >= k) {
minLength = Math.min(minLength, i - deque.shift());
}
// Maintain the deque in increasing order of prefix sums
while (deque.length > 0 && prefixSum[i] <= prefixSum[deque[deque.length - 1]]) {
deque.pop();
}
// Add the current index to the deque
deque.push(i);
}
return minLength === Infinity ? -1 : minLength;
}
前缀总和:
我们计算一个运行总和(prefixSum[i]),以便可以通过 prefixSum[j] - prefixSum[I] 计算从 i 到 j 的任何子数组的总和。
Deque:以递增顺序存储前缀和的索引。它帮助我们高效地找到总和大于或等于 k 的子数组。
缩小窗口:每当当前前缀和与双端队列中最小前缀和之间的差值大于或等于k时,我们通过从双端队列中删除最左边的索引来从左开始缩小窗口。
时间复杂度:O(n):
每个元素最多在双端队列中添加和删除一次,使解决方案在时间复杂度上呈线性。