一. 题目

二. 思路

• 双指针

• 优化：用一个diff记录cnts和cntt差异数，当差异为0时，表示cntss包含cntt，这样无需循环检查两个数组。

• O（m+n）

三. 代码

class Solution
{
    static final int N = 150, INF = Integer.MAX_VALUE;
    int[] cnts = new int[N], cntt = new int[N];

    public String minWindow(String s, String t)
    {
        int diff = 0;
        for (Character c : t.toCharArray())
            if (++cntt[c] == 1)//第一次出现时，统计差异数
                ++diff;

        int ansl = -1, len = Integer.MAX_VALUE;//记录起点和长度
        for (int l = 0, r = 0; r < s.length(); ++r)
        {
            int c = s.charAt(r);
            if (++cnts[c] == cntt[c]) --diff;//第一次相等，则减少差异
            while (diff == 0)//当差异为0时，左指针可以右移
            {
                if (r - l + 1 < len)
                {
                    len = r - l + 1;
                    ansl = l;
                }

                c = s.charAt(l++);
                if (--cnts[c] < cntt[c]) ++diff;//若l右移，导致不满足了，则差异变大
            }
        }
        return ansl == -1 ? "" : s.substring(ansl, ansl + len);
    }
}