Skip to content

Latest commit

 

History

History

2831.Find-the-Longest-Equal-Subarray

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 

2831.Find-the-Longest-Equal-Subarray

我们遍历数组,收集每种不同元素出现的位置。

假设对于元素A,它出现的所有的index都放入pos数组里。那么对于以pos[i]为左边界的subarray,我们向右寻找一个最远的pos[j],使得两个位置之间的“非A元素”的数量恰好小于等于k,那么就意味着这个区间可以通过有限的删除操作变成equal A的subarray。数学表达式为:

if (pos[j]-pos[i]+1 - (j-i+1) <= k)
   ret = max(ret, j-i+1)

显然,随着i的移动,j必然也是单向移动的。所以在pos数组上的快慢指针的移动,可以找出所有符合要求的区间,找到其中A元素最多的一段。

同理,处理其他的元素对应的pos数组,返回全局最大的解。