讨论/求职面试/面试题|面试题一例,面试官说用动态规划求解,实在没想明白。/
面试题|面试题一例,面试官说用动态规划求解,实在没想明白。

数组里有值为小于n的数组成,找出包含所有0~n-1个数的最小区间。例如:
array = [1,2,0,0,1,2,3,4,1]
n = 5

1

为啥要用动态规划,直接双指针滑动窗口+哈希表O(n)时间解决。哈希map统计每个数的出现次数,不断右移j枚举新位置,如果map的size到达n,那么此时[i,j]就是一个包含n种数的区间,然后右移i(相应得减去每个数的出现次数),更新最小区间长度,直到哈希表size不足n为止,继续右移j。

展开全部 13 讨论