如何找到和k的最大子数组

Question

假设您给出了一个大小为N的数组，它可以有正数和负数。我们需要返回总和的最大子数组的长度等于k。我尝试使用滑动窗口算法，但很快我发现它在这里不起作用，因为数组元素可以有正负整数。

例如：

arr=[-20，-38，-4，-7，10，4]和k = 3很明显，有两个可能的子阵列([-4，-7，10，4]和[-7，10])，它们的和等于给定的k。因此输出将是4(最大子阵列的长度)

蛮力方法将采取O(n^2)有没有更好的方法来做同样的问题？

Answer 1

您可以在geekforgeeks中找到有关问题的更多信息，“总和为k的最长子数组”。

朴素方法：考虑所有子数组的总和，并返回总和为“k”的最长子数组的长度。

时间复杂度为O（n^2）。

有效的方法是（使用哈希表）：

• 初始化sum=0和maxLen=0。
• 创建一个包含（sum， index）元组的哈希表。
• 对于i=0到n-1，执行以下步骤：
  • 将arr[i]累加到总和
  • 如果sum==k，更新maxLen=i 1。
  • 检查sum是否存在于哈希表中。如果不存在，则将其作为（sum， i）对添加到哈希表中。
  • 检查（sum-k）是否存在于哈希表中。如果存在，则从哈希表中获取（sum-k）的索引作为索引。现在检查maxLen是否

  时间复杂度：O（N），其中N是给定数组的长度。

  辅助空间：O（N），用于在HashMap中存储maxLlong。

  另一种方法

  这种方法不适用于负数。该方法是使用可变大小滑动窗口的概念，使用2个指针初始化I、j和sum = k。如果总和小于k，只增加j，如果总和等于k，计算最大值，如果总和大于k，当总和小于k时，减去第I个元素。

  时间复杂度：O（N），其中N是给定数组的长度。

  辅助空间:O(1)。

Answer 2

制作哈希表。

遍历数组，计算累积总和（从第0项到第i项），并将结果放入哈希表中，当前总和作为键，对于值-将索引插入到第一个和最后出现的对中，如下所示：{13：[2,19]}sum 13首先在索引2处满足，并且该总和的最右边位置是19。

然后再次扫描阵列。对于总和为 S 的索引 i，查找键 S k 的哈希表，然后选择最远的索引。例如，有索引5，总和6，k= 7，我们可以在上面的例子中找到最远的索引19。