。总和至少为 K 的最短子数组

862。总和至少为 K 的最短子数组

难度：难

主题：数组、二分查找、队列、滑动窗口、堆（优先级队列）、前缀和、单调队列

给定一个整数数组 nums 和一个整数 k，返回 总和至少为 k 的 nums 的最短非空子数组的长度。如果不存在这样的子数组，则返回-1.

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

示例1：

• 输入： nums = [1], k = 1
• 输出： 1

示例2：

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

示例 3：

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

约束：

• 1 5
• -10⁵ 5
• 1 9

解决方案：

我们需要使用滑动窗口方法结合前缀和和单调队列。以下是分步方法：

步骤：

1. 前缀和：

   • 首先，计算前缀和数组，其中索引 i 处的每个元素表示从数组开头到 i 的元素之和。前缀 sum 允许我们在常数时间内计算任何子数组的总和。

2. 单调队列：

   • 我们使用 deque（双端队列）来维护 prefix_sum 数组的索引。双端队列将以前缀和的递增顺序进行维护。
   • 这可以帮助我们通过比较当前前缀和与较早的前缀和来有效地找到总和大于或等于 k ​​的子数组。

3. 滑动窗口逻辑：

   • 对于每个索引 i，检查当前前缀和与任何先前前缀和（存储在双端队列中）之间的差异是否大于或等于 k。
   • 如果是这样，计算子数组的长度并根据需要更新最小长度。

算法：

1. 初始化大小为 n 1 的 prefix_sum 数组（其中 n 是输入数组的长度）。第一个元素为 0，因为零个元素的总和为 0。
2. 使用双端队列来存储 prefix_sum 值的索引。双端队列将有助于高效地找到满足条件的最短子数组。
3. 对于数组中的每个元素，更新 prefix_sum，并检查双端队列以找到 sum 大于或等于 k ​​的最小子数组。

让我们用 PHP 实现这个解决方案：862。总和至少为 K 的最短子数组

<?php
/**
 * @param Integer[] $nums
 * @param Integer $k
 * @return Integer
 */
function shortestSubarray($nums, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$nums1 = [1];
$k1 = 1;
echo shortestSubarray($nums1, $k1) . "\n"; // Output: 1

$nums2 = [1, 2];
$k2 = 4;
echo shortestSubarray($nums2, $k2) . "\n"; // Output: -1

$nums3 = [2, -1, 2];
$k3 = 3;
echo shortestSubarray($nums3, $k3) . "\n"; // Output: 3
?>

解释：

1. 前缀和数组：

   • 我们计算 prefix_sum 数组中数组的累积和。这有助于使用公式 prefix_sum[j 1] - prefix_sum[i].
   计算任何子数组 nums[i...j] 的总和

2. 单调队列：

   • 双端队列以值的递增顺序保存 prefix_sum 数组的索引。我们保持这个顺序，以便我们可以有效地找到总和大于或等于 k ​​的最小子数组。

3. 滑动窗口逻辑：

   • 当我们遍历 prefix_sum 数组时，我们尝试使用当前 prefix_sum[i] 和之前的 prefix_sum[deque[0]] 之间的差异来找到最小子数组。
   • 如果差值大于或等于 k，我们计算子数组长度并更新找到的最小长度。

4. 返回结果：

   • 如果没有找到有效的子数组，则返回-1。否则，返回最小子数组长度。

时间复杂度：

• 时间复杂度： O(n)，其中 n 是输入数组的长度。每个元素最多被处理两次（添加到双端队列时一次，删除时一次）。
• 空间复杂度： O(n)，由于 prefix_sum 数组和用于存储索引的双端队列。

这种方法确保即使对于大量输入，解决方案也能高效运行。

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是。总和至少为 K 的最短子数组的详细内容。更多信息请关注PHP中文网其他相关文章！