题目
给你一个整数数组 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] <= 1051 <= 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]的最大值
所以只需要找到 0~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;};
复制代码
评论