算法【Java】 —— 滑动窗口

在计算机科学中，滑动窗口是一种数据处理算法，常用于字符串和数组的问题中。它通过移动窗口内的“指针”来对数组或字符串的一部分进行操作，从而有效地处理大型数据集合。

以下是一个使用滑动窗口算法的Java代码示例，它找出字符串中最长的不含重复字符的子字符串的长度。

public class SlidingWindow {
    public static int lengthOfLongestSubstring(String s) {
        if (s.isEmpty()) {
            return 0;
        }
 
        int n = s.length();
        Set<Character> set = new HashSet<>();
        int left = 0, right = 0;
        int maxLength = 0;
 
        while (right < n) {
            if (!set.contains(s.charAt(right))) {
                set.add(s.charAt(right));
                right++;
                maxLength = Math.max(maxLength, right - left);
            } else {
                set.remove(s.charAt(left));
                left++;
            }
        }
 
        return maxLength;
    }
 
    public static void main(String[] args) {
        String s = "abcabcbb";
        System.out.println("The length of the longest substring without repeating characters is: " + lengthOfLongestSubstring(s));
    }
}

在这个例子中，我们使用一个哈希集合来跟踪我们已经看到的字符。左指针表示我们的滑动窗口的开始，右指针表示我们的滑动窗口的结束。我们的目标是不断地扩大窗口直到我们得到最长的不含有重复字符的字符串。如果我们遇到了一个重复的字符，我们就移除左指针所指向的字符，并继续滑动窗口。这个过程一直进行直到左指针无法再滑动。我们更新最大长度并重复这个过程直到我们遍历完整个字符串。