滑动窗口法（SlidingWindow）

适合场景
一般适用于解决字符串或数组的子串/子序列问题

思想

初始化左右指针，使它们都指向窗口的起始位置，同时初始化所需的变量和数据结构。
移动右指针，直到满足问题的要求，如找到了一个包含所需字符的子串或者满足某种条件的子数组。
移动左指针，缩小窗口，直到不能再满足问题的要求为止，同时更新所需的变量和数据结构。
重复步骤2和步骤3，直到右指针到达字符串或数组的末尾。

例题找数组中和为最大的连续数组
下面申明的数组，如果求和最大，那么为最大和为 1+2+3+5+7+1+2-1-2+3+4 = 25

        int[] nums = new int[]{1, 2, 3, 5, 7, 1, 2, -1, -2, 3, 4, -5};

 public static int getMaxNums(int[] nums) {
        //左指针
        int left = 0;
        //右指针
        int right = 0;
        //定义一个最小的值
        int max = Integer.MIN_VALUE;
        //定义当前相加的值
        int sum = 0;
        //一直移动右指针，右指针要小于数组的最大长度
        while (right < nums.length) {
            //计算当前相加的值（和+右指针的值）
            sum = sum + nums[right];
            //记录当前走过阶段获取到的最大的值
            max = Math.max(sum, max);
            // 当遇到 sum <0 的情况，就要左移，缩小窗口，知道窗口小到不满足问题要求
            while (left <= right && sum < 0) {
                left++;
                //缩小时要记得减去当前缩小的窗口的值
                max -= nums[left];
            }
            right++;
        }
        return max;
    }

最大值输出

例题找字符串中连续最长不重复的子串
定义一个字符串，其中最长的子串为：bcd

        String s = "aabbcdd";

下面我们来找最长的子串长度

public static int maxCharacter(String s) {
        //左指针
        int left = 0;
        //右指针
        int right = 0;
        //定义当前最大值
        int maxLen = 0;
        //定义set来添加不重复的字符
        Set<Character> set = new HashSet<>();
        while (right < s.length()) {
            //当set中不包含右指针指向的字符时，将字符加入set中
            if (!set.contains(s.charAt(right))) {
                set.add(s.charAt(right));
                //计算最大的字符长度
                maxLen = Math.max(maxLen, right - left + 1);
                right++;
            } else {
                //当set中包含右指针指向的字符时，set开始移除元素，left++，直到set中不包含重复元素
                set.remove(s.charAt(left));
                left++;
            }
        }
        return maxLen;
    }

最大长度的子串

如果要找最长长度的子串，那么其实加一个记录左指针的值就好了

 public static String getMaxCharacterS(String s) {
        int left = 0;
        int right = 0;
        int maxLen = 0;
        int position = 0;
        Set<Character> set = new HashSet<>();
        while (right < s.length()) {
            char a = s.charAt(right);
            if (!set.contains(a)) {
                set.add(a);
                if (right-left+1 > maxLen){
                    //记录左指针的位置
                    position = left;
                }
                maxLen = Math.max(maxLen, right - left+1);
                right++;
            } else {
                set.remove(s.charAt(left));
                left++;
            }
        }
        return s.substring(position, position+maxLen);
    }

最长子串的输出

最后编辑于：2023.04.02 20:34:33