2回答

ccmouse

2021-04-27

幼儿园化解释每条语句，这是个很合理的要求。

首先前面动画部分的算法理解了吗？

这里我们从左往右扫描一遍字符串，在扫描的过程中，我们计算：以从左到右每个位置 i 结尾的最长不重复子串的长度。为了计算，我们保持以下3点：

1. lastOccurred[ch]代表字符ch上一次出现的位置。

2. maxLength是到目前为止发现的最长不含重复字母子串。

3. 这个最难，在每次循环结束，也就是16行之后，17行之前，我们保证从start到i这个子串没有重复字符，并且是以i结束的没有重复字符子串中最长的一个。（也就是start-1到i这个子串必有重复字符，或者start是0。i之后的情况我们不知道，因为是从左往右扫描，所以还没有看到。）

我们仔细想一下，如果扫描中，i从0开始，一直到结束，我们始终保持上面三条的正确性，是不是最终结果就是maxLength? 这里必须想明白，才能看懂代码。这3条不要管怎么来的，我就是抛出这3条，你看如果它们始终正确，最终的maxLength是不是就是我们的答案：）

这个循环里的内容就是要做到保持这三点。

第8行，这里理解没问题。

lastI, ok := lastOccurred[ch]。这里只是第一次运行到是空（其实是0，参考我之前对于map的讲解），后面16行我们往lastOccurred里面写数据了，所以再下一次运行到这里不一定空。

if ok && lastI >= start 如果我们曾经见过ch(ok的作用)，并且ch上次出现的位置在start的右边（或者start位置）。

这是最关键的一行。我们看我们要维持的第3条，因为我们（假设）在上一个循环中维持了第3条的正确性，所以start到(i-1)这个子串没有重复字符。那我们可以说从start到i也没有重复字符吗？不能。因为lastOccurred[ch]告诉我们，我们现在看到的这个第i个字符，在start之后（或者start)出现过。那么为了维持第3条的正确性，我们必须说start=lastI+1。因为ch上次出现在lastI位置，所以从lastI+1之后，肯定没有ch。

接下来的代码就简单了。i-start+1，这是个简单的长度计算，从start开始（这里已经是更新后的start），到i结束（包括i），这个字符串的长度就是i-start+1，同学可以数一下。

最后我们更新lastOccurred[ch]，确保它的正确性。

========================================

建议同学结合调试器，或者每个循环进入的时候，打印start, 和lastOccurred，就能实际理解。

虽然我后面还会用到这些代码，但是讲述的是不同的知识点，后面再看到的时候，也可以无视这段代码的正确性，不过最好能够理解。

3

PhantomSoul

2022-03-12

lastOcrrured 他这里我觉得是做了一个字节和位置的映射。所以lastOccurred[ch]是一个数值。从0开始所以后面加1了。

0