[HOT 100] 0003. 无重复字符的最长子串

1. 题目链接

438. 找到字符串中所有字母异位词 - 力扣（LeetCode）

2. 题目描述

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

3. 题目示例

示例 1 :

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

示例 2 :

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

4. 解题思路

1. 初始化数据结构：

• ans：存储结果的列表，用来保存所有符合条件的起始位置。
• cntP：长度为 26 的数组，记录字符串 p 中每个字母的出现次数。这里假设字符串中的字符均为小写字母。
• cntS：长度为 26 的数组，记录当前窗口（即字符串 s 中一个子串）中每个字母的出现次数。
  
  

2. 统计 **p** 中字符的频次：

for (char c : p.toCharArray()) {
    cntP[c - 'a']++;
}

遍历字符串 p，根据每个字符的 ASCII 码值统计其出现次数。c - 'a' 将字母转化为数组下标（例如：'a' 对应下标 0，'b' 对应下标 1，依此类推）。

3. 滑动窗口遍历字符串 **s**：

for (int right = 0; right < s.length(); right++) {
    cntS[s.charAt(right) - 'a']++; // 右端点字母进入窗口
    int left = right - p.length() + 1;
    if (left < 0) { // 窗口长度不足 p.length()
        continue;
    }
    if (Arrays.equals(cntS, cntP)) { // s' 和 p 的每种字母的出现次数都相同
        ans.add(left); // s' 左端点下标加入答案
    }
    cntS[s.charAt(left) - 'a']--; // 左端点字母离开窗口
}

• **右指针 ****right**：从 0 遍历到 s.length() - 1，表示当前窗口的右端。
• **cntS[s.charAt(right) - 'a']++**：每次右指针移动时，更新窗口中的字符频次。
• **计算左指针 ****left**：left = right - p.length() + 1，计算窗口的左边界。如果窗口的长度小于 p.length()（即 left 小于 0），就跳过当前迭代，继续移动右指针。
• 判断是否为异位词：Arrays.equals(cntS, cntP) 比较当前窗口内字符的频次与字符串 p 的字符频次是否相同。如果相同，则说明找到了一个异位词子串，将其左端点 left 加入结果 ans。
• 左指针字母离开窗口：在每次遍历结束时，更新 cntS 数组，移除左端字符的频次：cntS[s.charAt(left) - 'a']--。
  
  

5. 题解代码

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans = new ArrayList<>();
        int[] cntP = new int[26]; // 统计 p 的每种字母的出现次数
        int[] cntS = new int[26]; // 统计 s 的长为 p.length() 的子串 s' 的每种字母的出现次数
        for (char c : p.toCharArray()) {
            cntP[c - 'a']++; // 统计 p 的字母
        }
        for (int right = 0; right < s.length(); right++) {
            cntS[s.charAt(right) - 'a']++; // 右端点字母进入窗口
            int left = right - p.length() + 1;
            if (left < 0) { // 窗口长度不足 p.length()
                continue;
            }
            if (Arrays.equals(cntS, cntP)) { // s' 和 p 的每种字母的出现次数都相同
                ans.add(left); // s' 左端点下标加入答案
            }
            cntS[s.charAt(left) - 'a']--; // 左端点字母离开窗口
        }
        return ans;
    }
}

6. 复杂度分析

• 时间复杂度: 遍历字符串 s 一次，时间复杂度为 O(n)，其中 n 是字符串 s 的长度。

• 在每次窗口滑动时，Arrays.equals(cntS, cntP) 的比较复杂度为 O(26)，即常数时间。

• 所以，总的时间复杂度是 O(n)。

• 空间复杂度: cntP 和 cntS 都是长度为 26 的数组，因此空间复杂度为 O(1)（常数空间）。