长度为 K 的不同子数组的最大和

2461。长度为 K

的不同子数组的最大和

难度：中等

主题：数组、哈希表、滑动窗口

给定一个整数数组 nums 和一个整数 k。求 nums 的所有子数组满足以下条件的最大子数组和：

• 子数组的长度为k，并且
• 子数组的所有元素不同。

返回满足条件的所有子数组的最大子数组和。如果没有子数组满足条件，则返回0.

子数组是数组中连续的非空元素序列。

示例1：

• 输入： nums = [1,5,4,2,9,9,9], k = 3
• 输出： 15
• 解释：长度为 3 的 nums 的子数组为：
  • [1,5,4]符合要求，总和为10。
  • [5,4,2]符合要求，总和为11。
  • [4,2,9]符合要求，总和为15。
  • [2,9,9]不符合要求，因为元素9重复。
  • [9,9,9]不符合要求，因为元素9重复。
  • 我们返回 15，因为它是所有满足条件子数组的最大子数组总和

示例2：

• 输入： nums = [4,4,4], k = 3
• 输出： 0
• 解释：长度为 3 的 nums 的子数组为：
  • [4,4,4]不符合要求，因为元素4重复。
  • 我们返回 0，因为没有 子数组满足条件。

约束：

• 1 5
• 1 5

提示：

1. 从以索引 i 结尾的大小为 k 的子数组移动到以索引 i 1 结尾的大小为 k 的子数组时，哪些元素会发生变化？
2. 只有两个元素发生变化，i 1 处的元素被添加到子数组中，i - k 1 处的元素从子数组中删除。
3. 迭代大小为 k 的每个子数组，并跟踪子数组的总和以及每个元素的频率。

解决方案：

我们可以按照以下步骤操作：

方法：

1. 滑动窗口：窗口大小为k，我们在数组中滑动窗口，同时维护当前窗口的总和并检查窗口中的所有元素是否不同。
2. 哈希表（或关联数组）：使用关联数组（哈希表）来跟踪当前窗口中元素的频率。如果任何元素出现多次，则该窗口无效。
3. 更新窗口：当我们滑动窗口时，添加新元素（即进入窗口的元素），并删除旧元素（即离开窗口的元素）。相应地更新总和并检查窗口是否有效（即所有元素都是不同的）。
4. 返回最大和：我们需要跟踪有效子数组中遇到的最大和。

算法：

1. 初始化一个哈希表freq，用于存储当前窗口中元素出现的频率。
2. 首先计算大小为 k 的第一个窗口的总和，如果窗口包含不同元素，则存储结果。
3. 从左向右滑动窗口：
   • 删除左侧离开窗口的元素。
   • 添加从右侧进入窗口的元素。
   • 更新总和和哈希表，并检查窗口是否仍然只包含不同的元素。
4. 如果窗口具有有效的不同元素，则更新最大总和。
5. 如果没有找到有效的子数组，则返回0。

让我们用 PHP 实现这个解决方案：2461。长度为 K
的不同子数组的最大和

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

// Example usage:
$nums1 = [1,5,4,2,9,9,9];
$k1 = 3;
echo maximumSubarraySum($nums1, $k1); // Output: 15

$nums2 = [4,4,4];
$k2 = 3;
echo maximumSubarraySum($nums2, $k2); // Output: 0
?>

解释：

1. 变量:

   • $maxSum：跟踪迄今为止找到的有效子数组的最大和。
   • $currentSum：保存当前大小为k的滑动窗口的总和。
   • $freq：哈希表（或关联数组），存储当前窗口中元素的频率。

2. 滑动窗口:

   • 我们用循环遍历数组。当我们移动窗口时，我们：
     • 将索引 $i 处的元素添加到总和中并更新其频率。
     • 如果窗口大小超过 k，我们从总和中删除索引 $i - k 处的元素并降低其频率。

3. 有效窗口检查：

   • 一旦窗口大小达到 k（即，当 $i >= k - 1 时），我们通过确保频率图中不同键的数量等于 k ​​来检查窗口中的所有元素是否不同。如果是，我们会更新最大总和。

4. 返回结果:

   • 迭代数组后，我们返回找到的最大总和。如果没有找到有效的子数组，maxSum 将保持为 0。

时间复杂度：

• O(n)，其中 n 是 nums 数组的长度。每个元素在滑动窗口中添加和删除一次，哈希表操作（插入、删除、检查计数）平均为 O(1)。

空间复杂度：

• O(k) 为存储当前窗口中元素出现频率的哈希表。

联系链接

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

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

• 领英
• GitHub

以上是长度为 K 的不同子数组的最大和的详细内容。更多信息请关注PHP中文网其他相关文章！