LeetCode 面试题 17.18. 最短超串

Categories:

题目描述
思路分析
1. 解法一：滑动窗口（推荐）
相似题目

题目描述

✅ 面试题 17.18. 最短超串

思路分析

解法一：滑动窗口（推荐）

核心思路：

small 中元素互不相同，可视为需要覆盖的目标集合。

用哈希表统计窗口内每个目标元素出现次数，并维护已满足的目标数 match。

右指针扩展窗口，满足全部目标后移动左指针尽量收缩，更新最短区间。

复杂度分析：

时间复杂度：O(n)，其中 n 为 big 的长度。

空间复杂度：O(k)，其中 k 为 small 的长度。

class Solution {
    public int[] shortestSeq(int[] big, int[] small) {
        Map<Integer, Integer> need = new HashMap<>();
        for (int num : small) {
            need.put(num, 1);
        }

        Map<Integer, Integer> window = new HashMap<>();
        int match = 0;
        int needSize = need.size();

        int left = 0;
        int bestL = -1;
        int bestR = -1;
        int bestLen = Integer.MAX_VALUE;

        for (int right = 0; right < big.length; right++) {
            int val = big[right];
            if (need.containsKey(val)) {
                int cnt = window.getOrDefault(val, 0) + 1;
                window.put(val, cnt);
                if (cnt == need.get(val)) {
                    match++;
                }
            }

            while (match == needSize && left <= right) {
                if (right - left + 1 < bestLen) {
                    bestLen = right - left + 1;
                    bestL = left;
                    bestR = right;
                }

                int drop = big[left];
                if (need.containsKey(drop)) {
                    int cnt = window.get(drop) - 1;
                    window.put(drop, cnt);
                    if (cnt < need.get(drop)) {
                        match--;
                    }
                }
                left++;
            }
        }

        if (bestL == -1) {
            return new int[0];
        }

        return new int[]{bestL, bestR};
    }
}

func shortestSeq(big []int, small []int) []int {
	need := map[int]int{}
	for _, num := range small {
		need[num] = 1
	}

	window := map[int]int{}
	match := 0
	needSize := len(need)

	left := 0
	bestL := -1
	bestR := -1
	bestLen := int(^uint(0) >> 1)

	for right, val := range big {
		if _, ok := need[val]; ok {
			window[val]++
			if window[val] == need[val] {
				match++
			}
		}

		for match == needSize && left <= right {
			if right-left+1 < bestLen {
				bestLen = right - left + 1
				bestL = left
				bestR = right
			}

			drop := big[left]
			if _, ok := need[drop]; ok {
				window[drop]--
				if window[drop] < need[drop] {
					match--
				}
			}
			left++
		}
	}

	if bestL == -1 {
		return []int{}
	}

	return []int{bestL, bestR}
}

相似题目

题目	难度	考察点
76. 最小覆盖子串	困难	滑动窗口
209. 长度最小的子数组	中等	滑动窗口
567. 字符串的排列	中等	滑动窗口
438. 找到字符串中所有字母异位词	中等	滑动窗口
727. 最小窗口子序列	困难	双指针

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/38501628