和至少为 K 的最短子数组

和至少为 K 的最短子数组

题目

给你一个整数数组 nums 和一个整数 k ,找出 nums 中和至少为 k 的 最短非空子数组 ,并返回该子数组的长度。如果不存在这样的 子数组 ,返回 -1 。

子数组 是数组中 连续 的一部分。

示例 1:

输入:nums = [1], k = 1
输出:1

示例 2:

输入:nums = [1,2], k = 4
输出:-1

示例 3:

输入:nums = [2,-1,2], k = 3
输出:3


提示:

1 <= nums.length <= 105
-105 <= nums[i] <= 105
1 <= k <= 109

题解

解题思路 题目给我们了一个数组,让我们求其中子数组和 不小于k的 最短的非空子数组

因为涉及到子数组和的问题,容易想到需要借助到前缀和数组 假设数组nums的前缀和数组为pre 且nums[i] = pre[i+1]-pre[i] 那么,原问题等价于在pre中求i、j的最小距离(0<=i<n,0<=j<n),满足i>j && pre[i]-pre[j] >= k

所以,我们可以枚举每个i,对于0~i位置,因为我们想求一个pre[i]-pre[j]的最大值

// 由于JavaScript中没有原生的双端队列,这里自己简单实现一个
class Dequeue {
constructor() {
// 数据域
this.data = []
// 头尾指针
this.head = 0
this.tail = -1
}
front() {
if (this.isEmpty()) return
return this.data[this.head]
}
back() {
if (this.isEmpty()) return
return this.data[this.tail]
}
pop_front() {
if (this.isEmpty()) return
this.adjust()
if (this.data.length == 1) {
this.head = 0
this.tail = -1
return this.data.pop()
}
return this.data[this.head++]
}
// 容量减少到一半,去掉冗余数据
adjust() {
if (this.size() * 2 < this.data.length) {
this.data = this.data.slice(this.head, this.tail + 1)
this.tail = this.data.length - 1
this.head = 0
}
}
pop_back() {
if (this.isEmpty()) return
this.adjust()
if (this.data.length == 1) {
this.head = 0
this.tail = -1
return this.data.pop()
}
return this.data[this.tail--]

}
size() {
return this.tail - this.head + 1
}
isEmpty() {
return this.size() <= 0
}
push(x) {
this.data[++this.tail] = x
}
}
var shortestSubarray = function (nums, k) {
const n = nums.length;
const pre = Array(n + 1).fill(0);
for (let i = 0; i < n; i++) pre[i + 1] = pre[i] + nums[i];
let res = n + 1;
const q = new Dequeue()
for (let i = 0; i <= n; i++) {
while (q.size() && pre[i] - pre[q.front()] >= k) {
res = Math.min(res, i - q.pop_front());
}
while (q.size() && pre[q.back()] >= pre[i]) q.pop_back();
q.push(i);
}
return res < n + 1 ? res : -1;
};
发表评论

相关文章