力扣热题 100：滑动窗口专题两道题详细解析（JAVA）

前言

昨晚健身玩臂力器，干到自己下巴了，给眼镜干飞出去20米，下巴也破了个小口，就是因为我没有带好保护绳，长记性了。

一、无重复字符的最长子串

1. 题目描述

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

2. 示例

示例 1：

输入：s = "abcabcbb"

输出：3

解释：因为最长的无重复字符子串是 "abc"，所以长度为 3。

示例 2：

输入：s = "bbbbb"

输出：1

解释：因为最长的无重复字符子串是 "b"，所以长度为 1。

示例 3：

输入：s = "pwwkew"

输出：3

解释：因为最长的无重复字符子串是 "wke"，所以长度为 3。

3. 解题思路

这道题主要考察滑动窗口的应用。我们可以使用滑动窗口来维护一个无重复字符的子串，通过移动窗口的左右边界来更新子串的长度。具体步骤如下：

1. 初始化两个指针 left 和 right，分别表示滑动窗口的左右边界。
2. 使用一个哈希表 map 来存储当前窗口内的字符及其索引。
3. 遍历字符串，对于每个字符 s[right]：
   • 如果该字符已经在哈希表中存在，且其索引大于等于 left，则移动 left 指针到该字符的下一个位置。
   • 更新哈希表中该字符的索引为 right。
   • 计算当前窗口的长度 right - left + 1，并更新最大长度。
4. 重复步骤 3，直到 right 遍历完整个字符串。

4. 代码实现（Java）

import java.util.HashMap;

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        int left = 0, right = 0, maxLength = 0;
        while (right < s.length()) {
            char c = s.charAt(right);
            if (map.containsKey(c) && map.get(c) >= left) {
                left = map.get(c) + 1;
            }
            map.put(c, right);
            maxLength = Math.max(maxLength, right - left + 1);
            right++;
        }
        return maxLength;
    }
}

5. 复杂度分析

• 时间复杂度 ：O(n)，其中 n 是字符串的长度。我们只需要遍历字符串一次，每次移动指针的时间复杂度都是 O(1)。
• 空间复杂度 ：O(min(n, m))，其中 m 是字符集的大小。在最坏情况下，哈希表中存储了所有字符。

二、找到字符串中所有字母异位词

1. 题目描述

给定两个字符串 s 和 p，找到 s 中所有 p 的字母异位词的起始索引。字母异位词指的是包含相同字符且每个字符出现次数相同的字符串。

2. 示例

示例 1：

输入：s = "cbaebabacd", p = "abc"

输出：[0, 6]

解释：起始索引为 0 的子串是 "cba"，起始索引为 6 的子串是 "bac"。

示例 2：

输入：s = "abab", p = "ab"

输出：[0, 1, 2]

解释：起始索引为 0 的子串是 "ab"，起始索引为 1 的子串是 "ba"，起始索引为 2 的子串是 "ab"。

3. 解题思路

这道题主要考察滑动窗口的应用。我们可以使用滑动窗口来维护一个固定长度的子串，通过移动窗口的左右边界来检查子串是否是字母异位词。具体步骤如下：

1. 初始化两个指针 left 和 right，分别表示滑动窗口的左右边界。
2. 使用两个数组 window 和 target 来存储当前窗口内的字符计数和目标字符串的字符计数。
3. 遍历字符串 s，对于每个字符 s[right]：
   • 更新当前窗口内的字符计数 window。
   • 如果窗口的大小等于目标字符串的长度，检查 window 和 target 是否相等。
   • 如果相等，记录当前窗口的起始索引。
   • 移动 left 指针，更新当前窗口内的字符计数 window。
4. 重复步骤 3，直到 right 遍历完整个字符串。

4. 代码实现（Java）

public class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        int[] window = new int[26];
        int[] target = new int[26];
        for (char c : p.toCharArray()) {
            target[c - 'a']++;
        }
        int left = 0, right = 0;
        while (right < s.length()) {
            window[s.charAt(right) - 'a']++;
            if (right - left + 1 == p.length()) {
                if (Arrays.equals(window, target)) {
                    result.add(left);
                }
                window[s.charAt(left) - 'a']--;
                left++;
            }
            right++;
        }
        return result;
    }
}

5. 复杂度分析

• 时间复杂度 ：O(n)，其中 n 是字符串 s 的长度。我们只需要遍历字符串一次，每次移动指针的时间复杂度都是 O(1)。
• 空间复杂度 ：O(1)，我们只使用了固定大小的数组来存储字符计数。

以上就是力扣热题 100 中与滑动窗口相关的两道题的详细解析，希望对大家有所帮助。在实际刷题过程中，建议大家多动手实践，理解解题思路的本质，这样才能更好地应对各种算法问题。