algorithm - 滑动窗口时间复杂度

Question

我有这个滑动窗口算法来解决问题；给定一个字符串 s 和一个非空字符串 p，找到 s 中 p 的字谜的所有起始索引。人们说这个算法的运行时间是 o(len(s))，如果我理解正确的话，我想确认一下。

所以外部 while 是 o(len(s))(假设 map 查找是 o(1))，内部 while 循环也可以运行 o(len(s )) 在最坏的情况下。例如，如果 S 是 axyzzzzzzzbc 并且 P 是 abc 那么内部 while 循环将起始指针移动到结束 所以它将是 o(len(s) + len(s)) 所以它是 o(2len(s)) 但我们放弃常量所以最终运行时间是o(len(s))。

请告诉我这是否正确。

public List<Integer> findAnagrams(String s, String p) {
    List<Integer> ret = new ArrayList<>();
    Map<Character, Integer> map = new HashMap<>();
    for (Character c : p.toCharArray()) {
        map.put(c, map.get(c) == null ? 1 : map.get(c) + 1);
    }
    int b = 0, i = 0;
    int c = map.size();
    while (i < s.length()) {
        if (map.containsKey(s.charAt(i))) {
            int t = map.get(s.charAt(i)) - 1;
            map.put(s.charAt(i), t);
            if (t == 0) c--;
        }
        i++;
        while (c == 0) {
            if (map.containsKey(s.charAt(b))) {
                int t = map.get(s.charAt(b)) + 1;
                map.put(s.charAt(b), t);
                if (t > 0) c++;
                    c++;
            }
            if (i - b == p.length()) {
                ret.add(b);
            }
            b++;

        }
    }
    return ret;

Answer 1

是的，复杂性是线性的。大多数字符被处理两次 - 除了最后的 M=p.length-1 字符。

所以 O(N + N - M) = O(N)