别小看“最短单词距离”，它其实是在教你如何把一次遍历用到极致

别小看“最短单词距离”，它其实是在教你如何把一次遍历用到极致

大家好，我是Echo_Wish。
今天聊一道看起来“人畜无害”，但非常适合用来检验算法基本功和工程思维的题目——
👉最短单词距离（Shortest Word Distance）。

很多人第一次看到这题，第一反应是：

“这不就查两个单词下标，算差值取最小吗？秒了。”

可现实往往是：
代码是写出来了，但思路是“凑”出来的。

而这道题，真正想考你的，其实是三个东西：

1. 你会不会用状态代替存储
2. 你有没有一次遍历的意识
3. 你能不能把“业务直觉”翻译成“算法逻辑”

我们慢慢聊。

一、先把题目翻译成人话

题目大意是这样的：

给你一个单词数组words，再给你两个不同的单词word1和word2，
求它们在数组中出现位置的最小距离。

举个例子：