java - 最小窗口子串我的解决方案的时间复杂度

Question

最小窗口子串

这是Leetcode https://leetcode.com/problems/minimum-window-substring/的一道题

我找到了一个基于滑动窗口算法的解决方案，但我无法计算出时间复杂度。有人说是O(N)，我觉得不是。请帮助我，谢谢!

    public class Solution {
    // Minimum Window Algorithm, the algorithm must fit for specific problem, this problem is diff from ...words
    // 348ms
    public String minWindow(String s, String t) {
        int N = s.length(), M = t.length(), count = 0;
        String res = "";
        if (N < M || M == 0)    return res;
        int[] lib = new int[256], cur = new int[256];  // ASCII has 256 characters
        for (int i = 0; i < M; lib[t.charAt(i++)]++);  // count each characters in t
        for (int l = 0, r = 0; r < N; r++) {
            char c = s.charAt(r);
            if (lib[c] != 0) {
                cur[c]++;
                if (cur[c] <= lib[c])   count++;
                if (count == M) {
                    char tmp = s.charAt(l);
                    while (lib[tmp] == 0 || cur[tmp] > lib[tmp]) {
                        cur[tmp]--;
                        tmp = s.charAt(++l);
                    }
                    if (res.length() == 0 || r - l + 1 < res.length()) 
                        res = s.substring(l, r + 1);
                    count--;  // should add these three lines for the case cur[c] c is char in s but not the one visited
                    cur[s.charAt(l)]--;
                    l++;
                }
            }
        }
        return res;
    }
 }

Answer 1

将s中的每个字符添加到r位置有N步

while操作符不超过O(N)个——至多N个工作周期有++l操作，至多N个无值(value)的检查while 条件

如果我们不考虑 s.substring，那么总体复杂度是线性的。

注意子串操作应该移出循环，我们必须只保留最好的索引对，并在最后得到子串。