Введение в алгоритм скользящего окна

алгоритм

предисловие

Недавно попал в leetCodeпроблема с алгоритмом, который включает в себя алгоритм скользящего окна, поэтому напишите статью, чтобы немного обобщить его.

Название описывает алгоритм

Максимальная длина подсимволов без повторяющихся символов: при заданной строке получить длину самого длинного подсимвола без повторяющихся символов.
пример:
Ввод: "abcabcbb"
выход: 3
Объяснение: Поскольку подсимвол без повторяющихся символов — «abc», длина — 3

Способ 1: Насильственное решение

    public class Solution {//时间复杂度高O(n3)
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int ans = 0;
        //遍历所有的子字符串，记录没有重复字母的子字符串的最大的长度
        //获取子字符串时，使用两个标签，分别代表子字符串的开头和结尾
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j <= n; j++)
                //当子字符串没有重复字母时，ans记录最大的长度
                if (allUnique(s, i, j)) ans = Math.max(ans, j - i);
        return ans;
    }
    //判断该子字符串是否有重复的字母
    public boolean allUnique(String s, int start, int end) {
        //HashSet实现了Set接口，它不允许集合中出现重复元素。
        Set<Character> set = new HashSet<>();
        for (int i = start; i < end; i++) {
            Character ch = s.charAt(i);
            if (set.contains(ch)) return false;
            set.add(ch);
        }
        return true;
    }
}

анализировать

Временная сложность: O(n3).

Решение 2. Алгоритм скользящего окна

При использовании HashSet в качестве скользящего окна проверка того, существует ли уже символ в существующих подсимволах, занимает всего O(1).
Скользящие окна часто используются как абстрактная концепция для решения проблем с массивами/строками. Окно представляет собой набор элементов данных/строки, определяемых индексом начала и конца.

public class Solution {//时间复杂度O(2n)
  //滑动窗口算法
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        Set<Character> set = new HashSet<>();
        int ans = 0, i = 0, j = 0;
        while (i < n && j < n) {//窗口的左边是i，右边是j，下列算法将窗口的左右移动，截取出其中一段
            // try to extend the range [i, j]
            if (!set.contains(s.charAt(j))){//如果set中不存在该字母，就将j+1，相当于窗口右边向右移动一格，左边不动
                set.add(s.charAt(j++));
                ans = Math.max(ans, j - i);//记录目前存在过的最大的子字符长度
            }
            else {//如果set中存在该字母，则将窗口左边向右移动一格，右边不动，直到该窗口中不存在重复的字符
                set.remove(s.charAt(i++));
            }
        }
        return ans;
    }
}

анализировать

Временная сложность: O(2n). В худшем случае каждый символ будет доступен дважды

Оптимизация алгоритма скольжения окна: решение 3

Приведенный выше алгоритм скользящего окна занимает не более 2n шагов, но на самом деле его можно оптимизировать так, чтобы он выполнял только n шагов. Мы можем использовать HashMap для определения сопоставления между символами и индексами, а затем, когда мы находим повторяющиеся символы в подстроке, мы можем напрямую пропускать пройденные символы.

public class Solution {//时间复杂度o(n)
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        //使用hashmap记录遍历过的字符的索引，当发现重复的字符时，可以将窗口的左边直接跳到该重复字符的索引处
        Map<Character, Integer> map = new HashMap<>(); // current index of character
        // try to extend the range [i, j]
        for (int j = 0, i = 0; j < n; j++) {//j负责向右边遍历，i根据重复字符的情况进行调整
            if (map.containsKey(s.charAt(j))) {//当发现重复的字符时,将字符的索引与窗口的左边进行对比，将窗口的左边直接跳到该重复字符的索引处
                i = Math.max(map.get(s.charAt(j)), i);
            }
            //记录子字符串的最大的长度
            ans = Math.max(ans, j - i + 1);
            //map记录第一次遍历到key时的索引位置，j+1,保证i跳到不包含重复字母的位置
            map.put(s.charAt(j), j + 1);
        }
        return ans;
    }
}

анализировать

Временная сложность: O(n)

Сводка алгоритмов скольжения окон

  • Алгоритм скольжения окон можно использовать для решения проблем массива / строки
  • Алгоритм скользящего окна может преобразовать проблему вложенного цикла for в задачу с одним циклом и уменьшить временную сложность.
Категории