最短超串

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

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

示例 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
通过次数3,853提交次数8,874

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shortest-supersequence-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
    public int[] shortestSeq(int[] big, int[] small) {

        Map<Integer, Integer> window = new HashMap<>();
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < small.length; i++) {
            set.add(small[i]);
        }
        int minLen = big.length + 1;
        int[] res = new int[2];

        for (int l = 0, r = 0; r < big.length; r++) {
            if (set.contains(big[r])) {
                window.put(big[r], window.getOrDefault(big[r], 0) + 1);     // 当window没有满的时候，继续向window中加入
                while (window.size() == set.size()) {                       // 当window满的时候，开始左边界右移
                    if (set.contains(big[l])) {
                        int num = window.get(big[l]);                       // 如果左边界的数等于window中某个数
                        if (num == 1) {                                     // 并且这个数在window中的数量是1
                            window.remove(big[l]);                          // 移除这个数
                            if (r - l + 1 < minLen) {                       // 如果当前的最小长度小于原先的最小长度
                                res[0] = l;                                 // 更新左右边界
                                res[1] = r;
                                minLen = r - l + 1;                         // 更新最小长度
                            }

                        } else {
                            window.put(big[l], window.get(big[l]) - 1);     //将这个数的数量减1
                        }

                    }
                    l++;

                }
            }
        }
        if (small.length > 1) return res[0] == res[1] ? new int[]{} : res;
        else return res;
    }
}

赏

谢谢你请我吃糖果

微信