P25. 没有重复字符的最长子串长度

https://algocasts.io/episodes/XOp1ZW2e

如何才會出現 i = Math.max(index[s.charAt(j)] + 1, i) 的這種情況呢?沒怎麼想明白。好像 abca 便是像這樣的一種可能,比如是 i 在 2, 然後 j 在 3 這樣的,那麼遇到了重複字符串,那便是不跳。好像是挺有道理的,但是如何產生 abca 且符合 i, j 位置的排列呢? abca 放在開始必然是不合適的,此時 i 不會移動,只會守住 0 位置。那麼只有在前面排了,研究一下 i 是怎麼排到 2 位置的,必然是依據同樣的算法跳到 2 位置的,即因爲 b 重複了,所以跳到 b 的下一位,比如 babca。所以此時需要取最大,不過取了之後的當次 ij 大了啊。不知道有沒有分析對。

@punut

没有分析对。我举个简单的例子你看一下。字符串用视频中的例子:abcbadfe

当 j 从 a 移动到 c 时,i 一直都不会动,它唯一更新的语句来自位置跳转 i = Math.max(index[s.charAt(j)] + 1, i),此时的 i/j 位置和 index 数组是:

a b c b a d f e
i
    j

index:
a        0
b        1
c        2

下一步,当 j 走到第二个 b 时,index 中已经有 b 的位置了,所以下面这条语句拆解开来就是:

i = Math.max(index[s.charAt(j)] + 1, i)
i = Math.max(index['b'] + 1, 0) // i 此时仍然为 0
i = Math.max(1+1, 0) // b 已经出现过,且在 index 中的下标是 1
i = 2 // 所以这一步,i 直接跳到下标 2,也就是第一个 b 的下一个位置

这样看是不是可以理解了?

1赞