。总和至少为 K 的最短子数组-php教程-PHP中文网

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

Patricia Arquette

发布： 2024-11-21 01:04:12

原创

864 人浏览过

. Shortest Subarray with Sum at Least 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

解决方案：

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

步骤：

前缀和：
- 首先，计算前缀和数组，其中索引 i 处的每个元素表示从数组开头到 i 的元素之和。前缀 sum 允许我们在常数时间内计算任何子数组的总和。
单调队列：
- 我们使用 deque（双端队列）来维护 prefix_sum 数组的索引。双端队列将以前缀和的递增顺序进行维护。
- 这可以帮助我们通过比较当前前缀和与较早的前缀和来有效地找到总和大于或等于 k 的子数组。
滑动窗口逻辑：
- 对于每个索引 i，检查当前前缀和与任何先前前缀和（存储在双端队列中）之间的差异是否大于或等于 k。
- 如果是这样，计算子数组的长度并根据需要更新最小长度。

算法：

初始化大小为 n 1 的 prefix_sum 数组（其中 n 是输入数组的长度）。第一个元素为 0，因为零个元素的总和为 0。
使用双端队列来存储 prefix_sum 值的索引。双端队列将有助于高效地找到满足条件的最短子数组。
对于数组中的每个元素，更新 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
?>

登录后复制

解释：

前缀和数组：
- 我们计算 prefix_sum 数组中数组的累积和。这有助于使用公式 prefix_sum[j 1] - prefix_sum[i].
单调队列：
- 双端队列以值的递增顺序保存 prefix_sum 数组的索引。我们保持这个顺序，以便我们可以有效地找到总和大于或等于 k 的最小子数组。
滑动窗口逻辑：
- 当我们遍历 prefix_sum 数组时，我们尝试使用当前 prefix_sum[i] 和之前的 prefix_sum[deque[0]] 之间的差异来找到最小子数组。
- 如果差值大于或等于 k，我们计算子数组长度并更新找到的最小长度。
返回结果：
- 如果没有找到有效的子数组，则返回-1。否则，返回最小子数组长度。