有个内含单词的超大文本文件，给定任意两个不同的单词，找出在这个文件中这两个单词的最短距离(相隔单词数)。如果寻找过程在这个文件中会重复多次，而每次寻找的单词不同，你能对此优化吗?

示例：
输入：words = ["I","am","a","student","from","a","university","in","a","city"], word1 = "a", word2 = "student"
输出：1

提示：
words.length <= 100000

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-closest-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路及方法

读题感觉很简单，一次遍历即可，但如果是直接遍历数组words，对于数组中的每个word1，遍历数组words 找到每个word2，并计算距离，该做法在最坏情况下的时间复杂度是 O(n^2)，需要优化。

优化的方式是：由于单词在words数组中位置是按升序存在的，所以之前已经计算过距离的，就不用再计算，因为距离肯定大于现在计算的两个单词距离。即从左到右遍历数组words，当遍历到word1时，如果已经遍历的单词中存在word2，为了计算最短距离，应该取最后一个已经遍历到的word2所在的下标，计算和当前下标的距离。同理，当遍历到word2时，应该取最后一个已经遍历到的word1所在的下标，计算和当前下标的距离，该算法时间复杂度是 O(n)。但是进阶要求如果寻找过程在这个文件中会重复多次，而每次寻找的单词不同，你能对此优化吗?当看到文件很大，要求查找效率的时候，就用哈希表，因为查找效率高。

用一个哈希表记录每个单词出现的下标，然后调用该函数时传入两个单词的参数，最后用双指针计算下标中的最小距离。

class Solution {
    public int findClosest(String[] words, String word1, String word2) {
        int n = words.length;
        if (n < 2) return 0;

        Map<String, List<Integer>> pos = new HashMap<>();
        // 遍历words按升序记录每个单词的所有位置
        for (int i = 0; i < n; i++) {
            String str = words[i];
            List<Integer> list = pos.getOrDefault(str, new ArrayList<>());
            list.add(i);
            pos.put(str, list);
        }

        // 计算最短距离
        int min = Integer.MAX_VALUE;
        for (int pos1 : pos.get(word1)) {
            for (int pos2 : pos.get(word2)) {
                min = Math.min(min, Math.abs(pos1 - pos2));
            }
        }
        
        return min;
    }
}

结果如下：