长度为 K 的不同子数组的最大和-php教程-PHP中文网

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

Susan Sarandon

发布： 2024-11-23 19:02:12

原创

458 人浏览过

Maximum Sum of Distinct Subarrays With Length 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，因为没有 子数组满足条件。

约束：

提示：

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

解决方案：

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

方法：

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

算法：

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

登录后复制

解释：

变量:
- $maxSum：跟踪迄今为止找到的有效子数组的最大和。
- $currentSum：保存当前大小为k的滑动窗口的总和。
- $freq：哈希表（或关联数组），存储当前窗口中元素的频率。
滑动窗口:
- 我们用循环遍历数组。当我们移动窗口时，我们：
  - 将索引 $i 处的元素添加到总和中并更新其频率。
  - 如果窗口大小超过 k，我们从总和中删除索引 $i - k 处的元素并降低其频率。
有效窗口检查：
- 一旦窗口大小达到 k（即，当 $i >= k - 1 时），我们通过确保频率图中不同键的数量等于 k 来检查窗口中的所有元素是否不同。如果是，我们会更新最大总和。
返回结果:
- 迭代数组后，我们返回找到的最大总和。如果没有找到有效的子数组，maxSum 将保持为 0。