单词距离

题目描述：

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

示例：

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

words.length <= 100000

思路:

时间复杂度：O(n),空间复杂度O(n)

把两个单词的坐标放入数组中，然后用双指针做

代码:

func findClosest(words []string, word1 string, word2 string) int {
    var a,b []int
    res := 99999
    for k,v := range words{
        if v == word1{
            a= append(a, k)
        }
        if v == word2{
            b = append(b,k)
        }
    }
    n1,n2 := len(a),len(b)
    l,r := 0,0
    for l< n1 && r < n2{
        if a[l]>b[r]{
            res = min(res, a[l]-b[r])
            r++
        }else{
            res = min(res, b[r]-a[l])
            l++
        }
    }
    return res
}

func min(a,b int)int{
    if a>b{
        return b
    }
    return a
}

代码效率：

执行用时：64 ms, 在所有 Go 提交中击败了98.57%的用户
内存消耗：11.2 MB, 在所有 Go 提交中击败了95.71%的用户