让我们假设给出了一个数组,您必须找到包含相同数量的字符和数字的最长的连续子数组。例如,我们有一个字符数组,例如('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)的时间复杂度来解决吗?
如果范围[x,y]具有与char相同的整数,则范围[0,x]和[0,y]的(num ints)-(num chars)具有相同的值。通过维护int vs chars累积差异的哈希,我们可以使用它来计算线性时间,线性空间中的答案。
longest_length
(最初为0)和start_index
(最初为nil)的轨迹longest_length
,然后适当更新。如果不是,请更新哈希。此结尾的答案是[start_index, start_index + longest_length]
。