当前位置：首页 > news >正文

腾讯云免费网站建设成都有哪些网站开发公司

news 2025/11/4 10:30:17

腾讯云免费网站建设,成都有哪些网站开发公司,有什么网站可以做外贸,南京市高淳区住房与城乡建设局网站什么是滑动窗口算法滑动窗口算法是一种用于解决数组（或字符串）中子数组（或子字符串）问题的算法。该算法通过维护一个固定大小的窗口（通常是两个指针），该窗口在数组上滑动，以寻找符…

什么是滑动窗口算法

滑动窗口算法是一种用于解决数组（或字符串）中子数组（或子字符串）问题的算法。该算法通过维护一个固定大小的窗口（通常是两个指针），该窗口在数组上滑动，以寻找符合特定条件的子数组。算法的基本思想是通过调整窗口的起始和结束位置来遍历整个数组，以找到满足特定条件的子数组。这个窗口通常是连续的，但具体的实现方式可以根据问题的要求而变化。

滑动窗口算法的一般步骤

滑动窗口算法的一般步骤如下：

初始化： 定义两个指针，通常表示窗口的起始位置（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;}// 用于存储字符和其在字符串中的位置HashMap<Character, 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算法

KMP（Knuth-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），来指导匹配过程中的跳跃。这个表记录了模式串每个前缀的最长相等前缀后缀的长度。
- 示例应用： 在文本编辑器中查找文本中的关键字等。