滑动窗口算法对于最长或者最短子数组的原理及其例子-DPDK中文网

滑动窗口算法是一种常见的解决子串、子序列问题的算法，它基于一个固定大小的窗口来扫描整个字符串。该算法可以用来解决最长或最短子数组问题。

原理：

初始化两个指针：left 和 right 指向第一个元素。
移动 right 指针来扩大窗口，直到窗口中包含所有需要解决问题的元素。
对窗口中的元素进行操作（计算最大值、最小值、求和等）。
移动 left 指针以缩小窗口，直到不再满足条件。
重复步骤2-4，直到 right 到达字符串的末尾。

例子：

最长无重复字符的子串

给定一个字符串 s，找出其中不含有重复字符的最长子串的长度。

示例 1:

输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

解题思路：

我们可以使用哈希集合 HashSet 来存储字符，判断一个字符是否出现过；定义指针left和right，分别代表无重复子串的左右指针；移动 right，如果 s[right] 在HashSet中不存在，将其加入 HashSet 中，并且将right右移；直到 s[right] 出现重复，此时不断移动 left 指针，直到重复的字符从 HashSet 中移除为止；更新无重复子串的长度；

Java代码实现：

public int lengthOfLongestSubstring(String s) {

Set<Character> set = new HashSet<>();
int n = s.length();
int right = 0, ans = 0;
for(int left=0; left<n; left++) {
    while(right<n && !set.contains(s.charAt(right))) {
        set.add(s.charAt(right));
        right++;
    }
    ans = Math.max(ans, right - left);      
    set.remove(s.charAt(left));
}
return ans;

}