给出一个由数字和字符组成的数组,找到两个相等的最长连续子数组[closed]

问题描述 投票:2回答:1

让我们假设给出了一个数组,您必须找到包含相同数量的字符和数字的最长的连续子数组。例如,我们有一个字符数组,例如('a',0,'v',2,4,7,'e','f','b',2,5,2,1)。

在那种情况下,最长的子数组将是('v',2,4,7,'e','f','b',2),因为它将是4个字符和4个数字。

我已经解决了类似的问题,例如“最大连续子数组问题”,但是我无法解决这个问题。同样,如果这是一个众所周知的问题,那么最好的解决方案是什么?有可能用O(n)的时间复杂度来解决吗?

arrays algorithm
1个回答
5
投票

如果范围[x,y]具有与char相同的整数,则范围[0,x]和[0,y]的(num ints)-(num chars)具有相同的值。通过维护int vs chars累积差异的哈希,我们可以使用它来计算线性时间,线性空间中的答案。

  1. 维护一个散列,最初为空,它将把计数的增量映射到索引。 (#ints-#chars)。例如7-> 22表示增量为7首次出现在索引22。
  2. 保持longest_length(最初为0)和start_index(最初为nil)的轨迹
  3. 解析数组,跟踪整数和字符的计数。
  4. 计算差异。检查您的哈希。如果它存在于哈希中,比较指标差异与您的longest_length,然后适当更新。如果不是,请更新哈希。

此结尾的答案是[start_index, start_index + longest_length]

© www.soinside.com 2019 - 2024. All rights reserved.