LeetCode 09 - 滑动窗口

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

方法：滑动窗口

使用左右两指针表示一个窗口，窗口中没有重复字符。每次向右移动 right 指针以扩大窗口范围，在该过程中：

• 如果最新添加的字符在窗口中不重复，则更新最大无重复子串的长度（len++）；
• 否则，不断向右移动 left 指针以缩小窗口范围，直到窗口中的子串不重复；
• 重复这个过程，直到 right 指针指向字符串结尾。

那么如何确定字符是否重复呢？可以使用 HashMap ，在添加新元素后，如果该元素的数量大于等于 2，则说明该字符重复。

int longestSubstring(String s) {
    int left = 0, right = 0, maxLen = 0;
    HashMap<Character, Integer> window = new HashMap<>();
    while(right < s.length()) {
        // 扩大窗口
        char c = s.charAt(right);
        right++;
        window.put(c, window.getOrDefault(c, 0) + 1);
        // 遇到重复字符，不断缩小窗口，直到不重复
        while(window.getOrDefault(c, 0) > 1) {
            char d = s.charAt(left);
            left++;
            window.put(d, window.get(d) - 1);
        }
        // 更新结果
        maxLen = Math.max(maxLen, right-left);
    }
    return maxLen;
}

扩大窗口和缩小窗口的操作是对称的。

209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [nums[l], nums[l+1], ..., nums[r-1], nums[r]] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

方法：滑动窗口

int minSubArrayLen(int[] nums, int target) {
    int left = 0, right = 0;
    int minLen = nums.length + 1;
    int window = 0;
    while(right < nums.length) {
        window += nums[right];
        right++;
        // 满足条件时更新 minLen，并尝试缩小窗口
        while(window >= target) {
            int len = right - left;
            minLen = Math.min(minLen, len);
            window -= nums[left];
            left++;
        } 
    }
    return (minLen > nums.length) ? 0 : minLen;
}

1004. 最大连续1的个数 III

给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。

方法：滑动窗口

记录左右指针确定的窗口范围内 0 的个数，在 right 指针右移的过程中：

• 当窗口内 0 的个数 count 不超过 k 时，根据当前窗口的宽度 更新最大窗口宽度；（count 等于需要反转的次数）
• 当窗口内 0 的个数 count 超过 k 时，开始 缩小窗口，left 指针右移，与此同时如果 left 处的数字为 0，则 count 减一。

int longestOnes(int[] nums, int k) {
    int n = nums.length;
    int result = 0;
    int left = 0, right = 0;
    int count = 0; // 窗口中 0 的个数
    while(right < n) {
        // 扩大窗口
        if(nums[right] == 0)
            count++;
        right++;
        // 翻转次数用光，开始缩小窗口
        while(count > k) {
            if(nums[left] == 0)
                count--;
            left++;
        }
        //更新最大长度
        result = Math.max(result, right - left);
    }
    return result;
}

1208. 尽可能使字符串相等

给你两个 长度相同 的字符串，s 和 t。

将 s 中的第 i 个字符变到 t 中的第 i 个字符需要 |s[i] - t[i]| 的开销（开销可能为 0），也就是两个字符的 ASCII 码值的差的绝对值。

用于变更字符串的最大预算是 maxCost。在转化字符串时，总开销应当小于等于该预算，这也意味着字符串的转化可能是不完全的。

如果你可以将 s 的子字符串转化为它在 t 中对应的子字符串，则返回可以转化的最大长度。如果 s 中没有子字符串可以转化成 t 中对应的子字符串，则返回 0。

方法：滑动窗口

利用左右两个指针记录窗口的左右边界，在逐步扩大窗口的过程中记录总的 cost：

• 如果超出 maxCost，则开始缩小窗口，同时从总的 cost 中扣除左指针处的花费；
• 在没有超出 maxCost 时，更新已转换子串的最大长度。

public int equalSubstring(String s, String t, int maxCost) {
    int n = s.length();
    int left = 0, right = 0;
    int cost = 0;
    int maxLen = 0;
    while(right < n) {
        // 扩大窗口
        cost += Math.abs(s.charAt(right) - t.charAt(right));
        right++;
        while(cost > maxCost) {
            // 缩小窗口
            cost -= Math.abs(s.charAt(left) - t.charAt(left));
            left++;
        }
        maxLen = Math.max(maxLen, right - left);
    }
    return maxLen;
}

567. 字符串的排列

给定两个字符串 s1,s2 ，判断 s2 的排列是否为 s1 的某个子串。

方法：滑动窗口

使用 left, right 两个指针表示一个窗口：

• 首先不断右移 right 指针来扩大窗口，同时同步更新窗口对应的子串信息；
• 当窗口长度和 s2 一样时，判断当前窗口中的子串是否为需要的一个排列；如果不是，则右移 left 指针来缩小窗口，在缩小的同时更新窗口对应的子串信息。

boolean checkInclusion(String s1, String s2) {
    int len1 = s1.length(), len2 = s2.length();
    if(len1 < len2) return false;

    HashMap<Character, Integer> window = new HashMap<>();
    HashMap<Character, Integer> need = new HashMap<>();
    for(char c : s2.toCharArray())
        need.put(c, need.getOrDefault(c, 0)+1);

    int left = 0, right = 0;
    int validCharNum = 0; // 已覆盖的字符数
    while(right < len1) {
        // 不断扩大窗口
        char c = s1.charAt(right);
        right++;
        if(need.containsKey(c)) {
            window.put(c, window.getOrDefault(c, 0) + 1);
            if(window.get(c).equals(need.get(c))) 
                validCharNum++;
        }
        // 窗口长度达到 len2 时，检查是否是一个所需的排列
        if(right-left == len2) {
            // 所有字符均被覆盖，则说明是一个所需排列
            if(validCharNum = need.size()) return true;
            // 不满足条件则缩小窗口，从而右移窗口
            char d = s1.charAt(left);
            left++;
            if(need.containsKey(d)) {
                if(window.get(d).equals(need.get(d)))
                    validCharNum--;
                window.put(d, window.get(d)-1);
            }
        } // end of if
    } // end of while
    return false;
}

209. 长度最小的子数组

给定一个数组和一个目标值，求出满足 sum >= target 的最短子数组。

方法：滑动窗口。

int minSubArrayLen(int target, int[] nums) {
    int left = 0, right = 0, minLen = nums.length + 1;
    int sum = 0;
    while(right < nums.length) {
        sum += nums[right];
        right++;
        // 窗口满足条件时更新 minLen，并滑动窗口
        while(sum >= target) {
            if(right - left < minLen) minLen = right - left;
            sum -= nums[left];
            left++;
        }
    }
    return (minLen > nums.length) ? 0 : minLen;
}