程序员面试金典17.18_go_最短超串题目假设你有两个数组

题目【程序员面试金典17.18_go_最短超串】假设你有两个数组，一个长一个短，短的元素均不相同。
找到长数组中包含短数组所有的元素的最短子数组，其出现顺序无关紧要。
返回最短子数组的左端点和右端点，如有多个满足条件的子数组，返回左端点最小的一个。若不存在，返回空数组。
示例 1:输入:big = [7,5,9,0,2,1,3,5,7,9,1,1,5,8,8,9,7] small = [1,5,9] 输出: [7,10]
示例 2:输入: big = [1,2,3] small = [4] 输出: []
提示： big.length <= 100000
1 <= small.length <= 100000
解题思路分析1、滑动窗口；时间复杂度O(n) ，空间复杂度O(n)
文章插图
func shortestSeq(big []int, small []int) []int { res := make([]int, 0) m := make(map[int]int) for i := 0; i < len(small); i++ {m[small[i]]++ } total := len(m) j := 0 for i := 0; i < len(big); i++ {m[big[i]]--if m[big[i]] == 0 {total--}for total == 0 {m[big[j]]++if m[big[j]] > 0 {total++if len(res) == 0 || res[1]-res[0] > i-j {res = []int{j, i}}}j++} } return res}总结Medium题目，滑动窗口题目