携程5.27笔试第二题（抽奖序列）

import java.util.HashMap;
import java.util.Map;

public class Main2 {
    static int winner(int[] s, int[] t) {
        int len = s.length;
        Map<Integer, Integer> window = new HashMap<>();
        Map<Integer, Integer> needs = new HashMap<>();
        for (int a : t) {
            needs.put(a, needs.getOrDefault(a, 0) + 1);
        }
        int left =0;
        int right = 0;
        // 最短序列的长度
        int res = Integer.MAX_VALUE;
        int valid = 0;
        // 起始位置
        int start = 0;
        while (right < len) {
            int a = s[right];
            right++;
            if (needs.containsKey(a)) {
                window.put(a, window.getOrDefault(a, 0) + 1);
                if (needs.get(a).equals(window.get(a))) {
                    valid++;
                }
            }
            while (needs.size() == valid) {
                if (right - left < res) {
                    start = left;
                    res = right - left;
                }
                int b = s[left];
                left++;
                if (needs.containsKey(b)) {
                    if (needs.get(b).equals(window.get(b))) {
                        valid--;
                    }
                    window.put(b, window.get(b) - 1);
                }
            }
        }
        return start == 0 ? 0 : start + 1;
    }

    public static void main(String[] args) {
        int[] s = {1,2,5,4,3,4,7,1,4,9,3,1};
        int[] t = {3,1, 4};
        System.out.println(winner(s, t));
    }
}