滑动窗口

滑动窗口也叫做“同向双指针”

适用条件：

1. 单调的（比如都是正数）
2. 针对于一个小区间内判断
3. 左边界与右边界是向相同方向移动

解题步骤：

1. 定义 left 与 right，令它们的值为 0
2. 进窗口，right++
3. 判断一下，如果满足条件出窗口，left++
4. 根据题目需要，更新结果

LC209. 长度最小的子数组

思路：

1. 分析题目，发现全是正数，而且是在一个区间内进行操作，就要想到滑动窗口
2. 进窗口，计算区间内的总和
3. 判断总和是否大于目标值，如果大于，那么记录一下当前长度，并且判断一下要不要更新结果
4. 出窗口，再次计算总和
5. 重复 2/3/4 循环，直到遍历结束

输入数据：

步骤： 0 / 0

当前动作：等待输入...

public int minSubArrayLen(int target, int[] nums) {
    // 使用滑动窗口来解决
    int n = nums.length;
    int ret = n + 1, left = 0, right = 0;
    int sum = 0;

    while (right < n) {
        if (sum < target) {
            sum += nums[right++];
        } else {
            // sum >= target
            int len = right - left;
            if (len < ret) ret = len;
            sum -= nums[left++];
        }
    }
    // 如果 sum >= target 那么就要判断一下
    while (sum >= target) {
        int len = right - left;
        if (len < ret) ret = len;
        sum -= nums[left++];

    }
    // 判断一下，是否应该输出 0
    // 判断一下是否满足
    if (ret == n + 1) ret = 0;
    return ret;
}

LC3. 无重复字符的最长子串

观察题目：发现有子串，可能会用到滑动窗口

画图：通过观察，发现 left 与 right 可以同时向右移动，那么就要想到滑动窗口了（重点）

思路：

1. 获取右边字符，rightV，接着判断哈希表内也没有包含 rightV
2. 如果不包含，那么就直接到下一个
3. 如果包含，那么就要获取到左边字符 leftV，判断是否与右边相等，如果不相等那么就一直删除哈希表中的 leftV

输入数据：

步骤： 0 / 0

当前动作：等待输入...

public int lengthOfLongestSubstring(String s) {
    // HashSet<Character> hash = new HashSet<>();
    boolean[] hash = new boolean[128]; // false 为没包含 true 为包含了
    int result = 0;

    // 定义左右指针
    int left = 0, right = 0;
    int n = s.length();
    while (right < n) {
        char rightV = s.charAt(right);
        if (!hash[rightV]) {
            right++;
            // hash.add(rightV);
            hash[rightV] = true;
        } else {
            // 包含
            // result = Math.max(hash.size(), result);
            result = Math.max(right - left, result);
            char leftV;
            while ((leftV = s.charAt(left)) != rightV) {
                // hash.remove(leftV);
                hash[leftV] = false;
                left++;
            }
            // 此时 leftV = rightV, 删除最后一个
            // hash.remove(leftV);
            hash[leftV] = false;
            left++;
        }
    }

    // return Math.max(hash.size(), result);
    return Math.max(right - left, result);
}

LC1004. 最大连续1的个数 III

思路：

1. 定义 left 与 right，如果 right 的值 rV != 0 的情况下，那么就只需要 right++ 即可
2. 如果 rV == 0，那么在之前的基础上判断 k 是否等于 0
   1. k != 0, 说明还可以把 0 翻转为 1, 那么就可以右移，不过需要 k--
   2. k == 0, 说明已经当前已经是最长的了，计算长度，保留最大值，接着将 left 右移，直到遇到值为 0 的情况才能停下来， 然后 left 跳过值为 0, k++

输入数据：

步骤： 0 / 0

当前动作：等待输入...

public int longestOnes(int[] nums, int k) {
    int n = nums.length;
    int ret = 0;
    int left = 0, right = 0;

    while (right < n) {
        int rV = nums[right];
        if (rV == 0) {
            // 判断一下 k 是否为 0
            if (k == 0) {
                // 说明已经达到最大值
                ret = Math.max(ret, right - left);
                // left 右移 直到找到为 0 值为止
                while (nums[left] != 0) {
                    left++;
                }
                // nums[left] == 0;
                left++;
                k++;
            } else {
                // 继续右移
                k--;
                right++;
            }
        } else {
            // rV == 1
            right++;
        }
    }

    // 最后在判断一下，防止没有进入 k == 0 的情况
    return Math.max(ret, right - left);
}

LC1658. 将 x 减到 0 的最小操作数

背景：

1. sum 为 [left, right) 这个区间内的总和
2. sumTotal 是数组 nums 所有元素的和

思路：

1. 读取题目，发现如果按照题目的方式做，那么是很困难的，因此要想到正难则反
   1. 题目中是求左右两边的和为 x，这个可以转换为求中间区间的和 sum，然后用 sumTotal - sum 这个值与 x 判断即可
   2. 这样可以把两个区间求和变成一个区间求和，难度递减
2. 这样就可以转变为长度最小的子数组类似的题目了：求 sum 与 target(sumTotal - x) 关系即可

输入数据：

步骤： 0 / 0

当前动作：等待输入...

public int minOperations(int[] nums, int x) {
    // 求出全部元素的和
    int sumTotal = 0, n = nums.length;
    for(int i = 0; i < n; i++) {
        sumTotal += nums[i];
    }

    int target = sumTotal - x, ret = n + 1;
    if (target < 0) return -1;
    
    int left = 0, right = 0;
    int sum = 0; // sum 是 [left, right) 这个区间内的元素之和
    while (right < n) {
        if (sum < target) {
            sum += nums[right++];
        } else if (sum == target) {
            // 更新返回值
            ret = Math.min(n - (right - left), ret);
            sum -= nums[left++];
        } else {
            // sum > target
            sum -= nums[left++];
        }
    }

    // 如果最后一个添加后, 比较大，那么还需要left右移
    while (sum > target) {
        sum -= nums[left++];    
    }
    // 最后判断一下
    if (sum == target) ret = Math.min(n - (right - left), ret);


    return ret == n + 1 ? -1 : ret;
}

LC904. 水果成篮

读题目，题目的意思就是：求最长的连续子数组，要求里面元素的类似不超过2

思路（暴力枚举）：

1. 遍历每个子数组，判断是否包含两种极其一下的数据
2. 如果包含，那么就 right++
3. 如果不包含，那么就记录并更新当前长度，接着 left++, right 重新遍历（优化点）

思路（优化）： 把“暴力枚举”的第3步优化一下，发现 right 不需要重新遍历，因为

​left++ 之前，[left, right] 区间内就已经是符合条件的， left++ 后，元素少一个那一定依然是符合条件的

输入数据：

步骤： 0 / 0

当前动作：等待输入...

public int totalFruit(int[] fruits) {
    // 定义类型
    int[] type = {-1, -1};
    // 每个类型对应的个数
    int[] count = {0, 0};
    int n = fruits.length, ret = -1;

    // [left, right) 是有效值
    int left = 0, right = 0;
    for(; right < n; right++) {
        int rV = fruits[right];
        if (type[0] == rV) {
            // 可以采摘
            count[0]++;
        } else if (type[1] == rV) {
            // 可以采摘
            count[1]++;
        } else if (type[0] == -1) {
            // 没有 type 没满
            type[0] = rV;
            count[0]++;
        } else if (type[1] == -1) {
            // 没有 type 没满
            type[1] = rV;
            count[1]++;
        } 
        else {
            // 说明类型已满 不能采摘了, 更新 ret
            ret = Math.max(ret, right - left);
            
            // 右移 left
            while (count[0] != 0 && count[1] != 0) {
                if (fruits[left] == type[0]) {
                    count[0]--;
                } else {
                    count[1]--;
                }
                left++;
            }
            // 判断哪个为0
            if (count[0] == 0) {
                count[0]++;
                type[0] = fruits[right];
            } else {
                count[1]++;
                type[1] = fruits[right];
            }
        }
    }
    // 考虑一路走到底的情况，比如全是 1
    return Math.max(right - left, ret);
}

LC438. 找到字符串中所有字母异位词

思路：

1. “异位词”判断：首先发现它不需要顺序，其次判断内部的值是否相等，那么就可以用 hash 表来判断，而不是通过排序来判断
2. 找到“异位词”，是找连续的区间，并且长度是与目标异位词相等，那么它左边与右边都是向右侧移动，就要想到滑动窗口

判断逻辑优化：

• 不要遍历hash表来判断，通过 totalValidCount 来判断，它是用来统计当前数组的有效数据的个数
• totalValidCount 更新：totalValidCount 加上 当前索引更新后的有效数据 - 当前索引更新前的有效数据
• 当前索引的有效数据获取：获取 pHash 与 sHash 的对应索引的较小值即可

输入数据：

步骤： 0 / 0

当前动作：等待输入...

public List<Integer> findAnagrams(String s, String p) {
    List<Integer> list = new ArrayList<>();
    int sN = s.length(), pN = p.length();
    if (sN < pN) return list;

    // 获取到 p 的 hash 表
    int[] pHash = new int[26];
    for (int i = 0; i < pN; i++) {
        pHash[p.charAt(i) - 'a']++;
    }

    int[] sHash = new int[26];
    int totalValidCount = 0; // 有效个数
    // [left, right)
    for(int left = 0, right = 0; right < sN; ) {
        // 进窗口
        while (right - left < pN) {
            totalValidCount = updateValidCount(s.charAt(right++) - 'a', sHash, pHash, 1, totalValidCount);
        }
        // 判断一下
        // 优化判断
        if (totalValidCount == pN) list.add(left);

        // 出窗口
        totalValidCount = updateValidCount(s.charAt(left++) - 'a', sHash, pHash, -1, totalValidCount);
    }

    return list;
}

// 传入的是更新之前的上下文
public int updateValidCount(int index, int[] sHash, int[] pHash, int updateVal, int totalValidCount) {
    int beforeValidCount = Math.min(sHash[index], pHash[index]); // 获取更新前的当前索引的有效个数
    sHash[index] += updateVal; // 更新 sHash 中的数值，
    int afterValidCount = Math.min(sHash[index], pHash[index]); // 获取更新后的当前索引的有效个数
    return totalValidCount + afterValidCount - beforeValidCount; // 返回的是最新的 totalValidCount
}

LC30. 串联所有单词的子串

思路：words 中的 word 看为字符为 1 的词，把 s 中各个子串也看为字符为 1 的词， 那么就和 找到字符串中所有字母异位词 的一样，都是不要求顺序，只找包含的内容

细节：

1. 滑动窗口执行的次数与 word 的长度一致
2. left 与 right 的步长也与 word 长度一致

输入数据：

步骤： 0 / 0

当前动作：等待输入...

public List<Integer> findSubstring(String s, String[] words) {
    int sN = s.length(), wN = words[0].length(), wsN = words.length;
    List<Integer> list = new ArrayList<>();

    HashMap<String, Integer> sMap = new HashMap<>(), wMap = new HashMap<>();
    // 计算 words 的有效个数
    for(String word : words) {
        if (!wMap.containsKey(word)) wMap.put(word, 1);
        else wMap.put(word, wMap.get(word) + 1);
    }

    int validCount = 0;
    int minus = wN * (wsN - 1);
    // 执行次数
    for (int i = 0; i < wN; i++) {
        for (int j = i; j <= sN - wN; j += wN) {
            String subS = s.substring(j, j + wN);
            // 入窗口
            if (!sMap.containsKey(subS)) sMap.put(subS, 1);
            else sMap.put(subS, sMap.get(subS) + 1);

            int sSubSCount = sMap.get(subS);
            validCount += Math.min(sSubSCount, wMap.getOrDefault(subS, 0)) 
                    - Math.min(sSubSCount - 1, wMap.getOrDefault(subS, 0));

            // 判断，看是否要进入
            if (validCount == wsN) list.add(j - minus);
            // 出窗口
            if (j - minus >= 0) {
                String removeS = s.substring(j - minus, j - minus + wN);
                sMap.put(removeS, sMap.get(removeS) - 1);
                validCount += Math.min(sMap.get(removeS), wMap.getOrDefault(removeS, 0)) 
                    - Math.min(sMap.get(removeS) + 1, wMap.getOrDefault(removeS, 0));
            }
        }

        // 滑动窗口结束 清理初始化 sMap 与 validCount
        sMap.clear();
        validCount = 0;
    }

    return list;
}

LC376. 最小覆盖子串

观察题目，发现是找连续的子串，要想到可能是涉及滑动窗口

问题思考：假设 [left, right] 是满足条件的区间，那么 left 右移后，right 需不需要重新从左开始移动呢？

不需要（left 与 right 同时向右移动，那么就可以用滑动窗口了）

1. 如果 [left + 1, right] 满足，那 right 不需要移动
2. 如果 [left + 1, right] 不满足条件，那么 right 是需要向右边移动

输入数据：

步骤： 0 / 0

当前动作：等待输入...

public String minWindow(String s, String t) {
    int sN = s.length(), tN = t.length();
    if (sN < tN) return "";

    HashMap<Character, Integer> tMap = new HashMap<>(), sMap = new HashMap<>();

    // 先统计tMap
    Character ch;
    for (int i = 0; i < tN; i++) tMap.put((ch = t.charAt(i)), tMap.getOrDefault(ch, 0) + 1);

    int left = 0, right = 0, retLeft = -1, retRight = 0;
    int validCountOfType = 0; // 有效的类型个数
    while (right < sN) {
        Character rCh = s.charAt(right++);
        sMap.put(rCh, sMap.getOrDefault(rCh, 0) + 1);
        // 进窗口后，判断一下个数是否满足
        if (sMap.get(rCh).equals(tMap.getOrDefault(rCh, 0))) validCountOfType++;

        if (validCountOfType == tMap.size()) {
            // validCountOfType == tMap.size() 不会存在大于的情况
            while (validCountOfType == tMap.size()) {
                // 出窗口
                Character lCh = s.charAt(left++);
                if (sMap.get(lCh).equals(tMap.getOrDefault(lCh, 0))) validCountOfType--;
                sMap.put(lCh, sMap.get(lCh) - 1);
            }
            // 此时就不满足了条件，但是[left - 1, right)是满足条件的
            if (retLeft == -1 || right - left + 1 < retRight - retLeft) {
                // 更新条件
                retLeft = left - 1;
                retRight = right;
            }
        }
    }

    String retS;
    if (retLeft == -1) retS = "";
    else retS = s.substring(retLeft, retRight);

    return retS;
}