一、题目描述

$\quad$题目大意参考： https://leetcode.cn/problems/shortest-supersequence-lcci/description/

二、算法：双指针

1. 时间复杂度：$O(N+M)$
2. 空间复杂度：$O(N+M)$

三、代码

class Solution {
    final int INF = 0x3f3f3f3f;
    int n, m;
    HashSet<Integer> hs;
    HashMap<Integer, Integer> cnt;
    HashMap<Integer, int[]> ans;
    {
        hs = new HashSet<>();
        cnt = new HashMap<>();
        ans = new HashMap<>();
    }

    public int[] shortestSeq(int[] big, int[] small) {
        int n = big.length, m = small.length;

        for(int i = 0; i < m; i++) {
            hs.add(small[i]);
        }

        for(int i = 0, j = 0; j < n; j++) {
            if(hs.contains(big[j])) {
                if(!cnt.containsKey(big[j])) {
                    cnt.put(big[j], 0);
                }
                cnt.put(big[j], cnt.get(big[j]) + 1);
            }

            while(cnt.size() == m) {
                if(!hs.contains(big[i])) {
                    i++;
                }
                else if(cnt.get(big[i]) > 1) {
                    cnt.put(big[i], cnt.get(big[i]) - 1);
                    i++;
                }
                else {
                    int len = j - i + 1;
                    if(!ans.containsKey(len)) {
                        ans.put(len, new int[] {i, j});
                    }
                    break;
                }
            }
        }
        if(ans.isEmpty()) {
            return new int[] {};
        }
        int len = INF;
        for(Integer key : ans.keySet()) {
            len = Math.min(len, key);
        }

        return ans.get(len);
    }
}