面试题 17.11. 单词距离

解法一

题中说明需要多次查询，但实际题目中并没有体现出来。用双指针一遍遍历在本题中是快速的方法，但是我认为这不符合原意。
用Map存储单词出现的下标序列，然后双指针找最小差值。其实两个下标序列都是有序的，找最小差值的时候可以使用二分查找进一步优化。

import java.util.*;
class Solution {
    public int findClosest(String[] words, String word1, String word2) {
        // 存储每个单词的位置序列
        Map<String, List<Integer>> wordIndexMap = new HashMap<>();
        int i = 0;
        for (i = 0; i < words.length; ++i) {
            if (wordIndexMap.containsKey(words[i])) {
                wordIndexMap.get(words[i]).add(i);
            } else {
                LinkedList<Integer> list = new LinkedList<>();
                list.add(i);
                wordIndexMap.put(words[i], list);
            }
        }
        List<Integer> indexList_1 = wordIndexMap.get(word1);
        List<Integer> indexList_2 = wordIndexMap.get(word2);
        Iterator<Integer> iterator_1 = indexList_1.iterator();
        Iterator<Integer> iterator_2 = indexList_2.iterator();
        int delta;
        int x = iterator_1.next();
        int y = iterator_2.next();
        int min = Math.abs(x - y);
        while ((iterator_1.hasNext()) && (iterator_2.hasNext())) {
            delta = x - y;
            min = Math.min(Math.abs(delta), min);
            if (delta < 0) {
                x = iterator_1.next();
            } else {
                y = iterator_2.next();
            }
        }
        min = Math.min(Math.abs(x - y), min);
        while (iterator_1.hasNext()) {
            min = Math.min(Math.abs(iterator_1.next() - y), min);
        }
        while (iterator_2.hasNext()) {
            min = Math.min(Math.abs(iterator_2.next() - x), min);
        }
        return min;
    }
}