自助建站门户网站,郑州最新情况,漳州建设企业网站,福永网站优化什么是滑动窗口算法
滑动窗口算法是一种用于解决数组#xff08;或字符串#xff09;中子数组#xff08;或子字符串#xff09;问题的算法。该算法通过维护一个固定大小的窗口#xff08;通常是两个指针#xff09;#xff0c;该窗口在数组上滑动#xff0c;以寻找符…什么是滑动窗口算法
滑动窗口算法是一种用于解决数组或字符串中子数组或子字符串问题的算法。该算法通过维护一个固定大小的窗口通常是两个指针该窗口在数组上滑动以寻找符合特定条件的子数组。算法的基本思想是通过调整窗口的起始和结束位置来遍历整个数组以找到满足特定条件的子数组。这个窗口通常是连续的但具体的实现方式可以根据问题的要求而变化。
滑动窗口算法的一般步骤
滑动窗口算法的一般步骤如下 初始化 定义两个指针通常表示窗口的起始位置left和结束位置right并初始化它们。 滑动窗口 移动右指针直到满足某个条件为止。这个条件可以根据具体问题而定比如找到一个符合要求的子数组或达到某种状态。 调整窗口大小 当右指针移动到某个位置后如果满足了条件尝试缩小窗口大小即移动左指针直到不再满足条件为止。 重复操作 不断重复步骤2和步骤3直到遍历完整个数组。
滑动窗口算法通常用于解决一些优化问题例如在一个数组中找到最短的子数组使得其满足特定的条件或者在一个字符串中找到最短的子串包含目标子串中的所有字符。这种算法的时间复杂度通常较低因为它避免了不必要的重复计算。
滑动窗口算法是如何实现的
下面我会以一个具体问题为例演示如何使用 Java 代码实现滑动窗口算法。我们以「找到字符串中无重复字符的最长子串」为例实现滑动窗口算法。
import java.util.HashMap;public class LongestSubstringWithoutRepeating {public static int lengthOfLongestSubstring(String s) {if (s null || s.length() 0) {return 0;}// 用于存储字符和其在字符串中的位置HashMapCharacter, Integer map new HashMap();int maxLength 0;int left 0;for (int right 0; right s.length(); right) {char currentChar s.charAt(right);// 如果字符已经在窗口中更新左指针的位置if (map.containsKey(currentChar)) {left Math.max(map.get(currentChar) 1, left);}// 更新字符的位置map.put(currentChar, right);// 更新最大长度maxLength Math.max(maxLength, right - left 1);}return maxLength;}public static void main(String[] args) {String input abcabcbb;int result lengthOfLongestSubstring(input);System.out.println(result); // 输出 3对应的无重复字符子串为 abc}
}上述代码实现了寻找字符串中无重复字符的最长子串的长度。核心是通过维护一个窗口用 left 和 right 指针表示窗口的左右边界通过遍历字符串不断调整窗口的大小同时利用哈希表记录每个字符最后一次出现的位置以实现快速的查找和更新。
什么是KMP算法
KMPKnuth-Morris-Pratt算法是一种用于在文本串中查找模式串出现位置的字符串匹配算法。它的主要特点是在匹配失败时能够利用已经得到的部分匹配结果避免不必要的比较从而提高匹配效率。
KMP算法的核心思想是构建一个部分匹配表Partial Match Table也称为「next数组」用于指导匹配过程中的跳跃。这个表记录了模式串中每个前缀的最长相等前缀后缀的长度。通过在匹配过程中利用这个表算法能够在匹配失败时迅速调整模式串的位置继续匹配而不用回溯到文本串中的前面位置。
KMP算法的基本步骤 构建部分匹配表 遍历模式串对于每个位置找到最长的相等的前缀后缀的长度并将这个长度记录在部分匹配表中。 匹配过程 在匹配文本串和模式串的过程中当匹配失败时根据部分匹配表中的值调整模式串的位置继续匹配。
KMP算法的时间复杂度是 O(m n)其中 m 是模式串的长度n 是文本串的长度。相比暴力匹配算法的 O(mn) 复杂度KMP算法在处理大规模文本串和模式串时具有更高的效率。
public class KMPAlgorithm {public static int[] buildNext(String pattern) {int[] next new int[pattern.length()];int j 0;for (int i 1; i pattern.length(); i) {while (j 0 pattern.charAt(i) ! pattern.charAt(j)) {j next[j - 1];}if (pattern.charAt(i) pattern.charAt(j)) {j;}next[i] j;}return next;}public static int kmpSearch(String text, String pattern) {int[] next buildNext(pattern);int j 0;for (int i 0; i text.length(); i) {while (j 0 text.charAt(i) ! pattern.charAt(j)) {j next[j - 1];}if (text.charAt(i) pattern.charAt(j)) {j;}if (j pattern.length()) {return i - j 1; // 匹配成功返回起始位置}}return -1; // 未找到匹配}public static void main(String[] args) {String text ABABCABAB;String pattern ABAB;int result kmpSearch(text, pattern);System.out.println(result); // 输出 2}
}这个示例中buildNext 方法用于构建部分匹配表而 kmpSearch 方法则实现了KMP算法的匹配过程。
二者有何区别
应用场景和实现原理有一些不同 滑动窗口算法 应用场景 主要用于解决子串问题即在一个字符串中找到一个连续的子串满足特定的条件。实现原理 通过维护一个可变大小的窗口该窗口在字符串上滑动同时根据问题的要求调整窗口的大小。该算法通常通过两个指针一个指向窗口的起始位置另一个指向窗口的结束位置来遍历整个字符串。示例应用 最小覆盖子串、最长无重复字符子串等问题。 KMP算法Knuth-Morris-Pratt算法 应用场景 主要用于在一个文本串中查找一个模式串的出现位置。实现原理 KMP算法利用了模式串中已匹配的信息避免不必要的回溯。它通过构建一个部分匹配表Partial Match Table来指导匹配过程中的跳跃。这个表记录了模式串每个前缀的最长相等前缀后缀的长度。示例应用 在文本编辑器中查找文本中的关键字等。
区别
问题类型 滑动窗口算法主要用于子串问题而KMP算法主要用于模式匹配问题。实现原理 滑动窗口算法通过维护一个窗口在字符串上的滑动来解决问题而KMP算法利用构建的部分匹配表来优化模式匹配过程。应用场景 滑动窗口算法更适用于连续的子串匹配问题而KMP算法更适用于在文本中查找模式串的位置。
总体而言虽然滑动窗口算法和KMP算法有不同的应用场景但它们都是在字符串处理领域中解决特定问题的有效工具。选择使用哪种算法取决于具体的问题需求。
