sliding-window-algorithm算法

发表于 | 分类于 | | 次阅读

滑窗算法

滑窗算法是通过使用特定大小的子列表，在遍历完整列表的同时进行特定的操作，以达到降低了循环的嵌套深度。

一般在找无重复最长子串，连续元素最大和等。

双指针移动，遍历时不嵌套循环所有值，外层遍历代表整个窗口向右滑动，每次减去失效值（重复值）加上最新值，比较长度。

例子：

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

示例 1:

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

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int left = 0;
        int right = 0;
        int max = 0;
        Set<Character> NoSameChar = new HashSet<>();
        
        while(left < s.length() && right < s.length()){
            if(!NoSameChar.contains(s.charAt(right))){
                NoSameChar.add(s.charAt(right));
                right++;
                max = max > right-left ? max : right - left;
            }else{
                NoSameChar.remove(s.charAt(left));
                left++;
            }
        }
        return max;
    }
}

参考：

滑窗详解

滑窗算法

0%