最短超串

/*
 * Problem: Given two arrays, one large and one small, where the elements of the small array are all unique. 
 * Find the shortest subarray in the large array that contains all elements of the small array, regardless of their order.
 * Return the left and right indices of the shortest subarray. If there are multiple such subarrays, return the one with the smallest left index.
 * If no such subarray exists, return an empty array.
 *
 * Example 1:
 * Input:
 * big = [7,5,9,0,2,1,3,5,7,9,1,1,5,8,8,9,7]
 * small = [1,5,9]
 * Output: [7,10]
 *
 * Example 2:
 * Input:
 * big = [1,2,3]
 * small = [4]
 * Output: []
 */

import java.util.*;
import java.util.stream.Collectors;

public class SolutionStream {
    public int[] shortestSeq(int[] big, int[] small) {
        Set<Integer> smallSet = Arrays.stream(small).boxed().collect(Collectors.toSet());
        Map<Integer, Long> countMap = Arrays.stream(small).boxed().collect(Collectors.groupingBy(e -> e, Collectors.counting()));
        Map<Integer, Long> windowMap = new HashMap<>();
        int left = 0, minLeft = 0, minRight = Integer.MAX_VALUE;
        for (int right = 0; right < big.length; right++) {
            if (smallSet.contains(big[right])) {
                windowMap.put(big[right], windowMap.getOrDefault(big[right], 0L) + 1);
            }
            while (windowMap.size() == countMap.size() && windowMap.entrySet().containsAll(countMap.entrySet())) {
                if (right - left < minRight - minLeft) {
                    minLeft = left;
                    minRight = right;
                }
                if (smallSet.contains(big[left])) {
                    windowMap.put(big[left], windowMap.get(big[left]) - 1);
                    if (windowMap.get(big[left]) == 0) windowMap.remove(big[left]);
                }
                left++;
            }
        }
        return minRight == Integer.MAX_VALUE ? new int[]{} : new int[]{minLeft, minRight};
    }
}