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

文章目录

- - 1. 题目链接
  - 2. 题目描述
  - 3. 题目示例
  - 4. 解题思路
  - 5. 题解代码
  - 6. 复杂度分析

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;}
}