gold-17-18

假设你有两个数组，一个长一个短，短的元素均不相同。找到长数组中包含短数组所有的元素的最短子数组，其出现顺序无关紧要。

返回最短子数组的左端点和右端点，如有多个满足条件的子数组，返回左端点最小的一个。若不存在，返回空数组。

示例 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

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[] shortestSeq(int[] big, int[] small) {
        int beg = 0;
        int end = 0;
        int bestBeg = -1;
        int bestEnd = -1;
        int shortestLen = Integer.MAX_VALUE;
        Map<Integer, Integer> smallMap = new HashMap<>();
        int matchedNum = 0;

        for (int one : small) {
            smallMap.put(one, 0);
        }

        while (end < big.length) {
            if (smallMap.containsKey(big[end])) {
                int lastNum = smallMap.get(big[end]);
                lastNum++;
                smallMap.put(big[end], lastNum);
                if (lastNum == 1) {
                    matchedNum++;
                }
            }

            while (matchedNum == small.length && beg <= end) {
                if ((end - beg + 1) < shortestLen) {
                    shortestLen = end - beg + 1;
                    bestBeg = beg;
                    bestEnd = end;
                }
                if (smallMap.containsKey(big[beg])) {
                    int lastNum = smallMap.get(big[beg]);
                    lastNum--;
                    smallMap.put(big[beg], lastNum);
                    if (lastNum == 0) {
                        matchedNum--;
                    }
                }
                beg++;
            }
            end++;
        }

        if (bestBeg == -1) {
            return new int[0];
        }
        int[] result = new int[2];
        result[0] = bestBeg;
        result[1] = bestEnd;
        return result;
    }
}
//leetcode submit region end(Prohibit modification and deletion)