DeepSeek LeetCode 438. 找到字符串中所有字母异位词 Java实现

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

题目理解

给定字符串 s 和 p，找出 s 中所有 p 的字母异位词 的起始索引。

· 字母异位词：字母种类和数量相同，顺序可不同
· 返回所有匹配子串的起始下标
· 子串长度固定为 p.length()

本质：固定长度滑动窗口 + 字符计数比较。

解法一：滑动窗口 + 数组计数（推荐，O(n)）

思路

窗口大小固定为 p.length()，每次向右滑动一格：

· 进窗：右边界字符计数 +1
· 出窗：左边界字符计数 -1
· 每滑动一步，比较窗口计数与 p 的计数是否完全一致

优化点：用 diff 变量记录"当前有几个字符的计数与 p 不一致"，避免每次比较整个数组（26 次）。

代码（数组 + diff 优化）

import java.util.ArrayList;
import java.util.List;

class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<>();
int n = s.length(), m = p.length();
if (n < m) return res;

int[] cntS = new int[26];
int[] cntP = new int[26];

// 统计 p 的字符计数，以及 s 中第一个窗口的计数
for (int i = 0; i < m; i++) {
cntP[p.charAt(i) – 'a']++;
cntS[s.charAt(i) – 'a']++;
}

// 计算初始窗口的差异数
int diff = 0;
for (int i = 0; i < 26; i++) {
if (cntS[i] != cntP[i]) diff++;
}
if (diff == 0) res.add(0);

// 滑动窗口
for (int i = m; i < n; i++) {
int in = s.charAt(i) – 'a'; // 进入窗口的字符
int out = s.charAt(i – m) – 'a'; // 离开窗口的字符

// —- 移出 out 字符，更新 diff —-
if (cntS[out] == cntP[out]) diff++; // 原本相等，移出后变不等
cntS[out]—;
if (cntS[out] == cntP[out]) diff—; // 移出后变相等

// —- 移入 in 字符，更新 diff —-
if (cntS[in] == cntP[in]) diff++; // 原本相等，移入后变不等
cntS[in]++;
if (cntS[in] == cntP[in]) diff—; // 移入后变相等

if (diff == 0) res.add(i – m + 1);
}

return res;
}
}

复杂度

· 时间：O(n + 26)，每个字符进出窗口各 O(1)，初始比较 O(26)
· 空间：O(1)，两个固定大小 26 的数组

解法二：滑动窗口 + 双指针（更简洁）

思路

维护一个窗口，保证窗口内每种字符的数量都不超过 p 中该字符的数量：

· 右指针扩张；若某字符计数超过 p 的限制，左指针收缩直到不超
· 当窗口长度 == m，说明正好是异位词

代码

import java.util.ArrayList;
import java.util.List;

class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<>();
int n = s.length(), m = p.length();
if (n < m) return res;

int[] need = new int[26];
for (char c : p.toCharArray()) need[c – 'a']++;

int[] window = new int[26];
int left = 0;

for (int right = 0; right < n; right++) {
int c = s.charAt(right) – 'a';
window[c]++;

// 窗口内该字符超出 p 的限制，收缩左边界
while (window[c] > need[c]) {
window[s.charAt(left) – 'a']—;
left++;
}

// 窗口长度正好为 m，就是异位词
if (right – left + 1 == m) {
res.add(left);
}
}

return res;
}
}

复杂度

· 时间：O(n)，每个字符至多进出窗口一次
· 空间：O(1)

解法三：固定窗口直接比较（最易读）

不做 diff 优化，每次直接比较两个计数数组。适合面试时快速写出。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<>();
int n = s.length(), m = p.length();
if (n < m) return res;

int[] cntP = new int[26];
int[] cntS = new int[26];
for (char c : p.toCharArray()) cntP[c – 'a']++;

for (int i = 0; i < n; i++) {
cntS[s.charAt(i) – 'a']++;
if (i >= m) cntS[s.charAt(i – m) – 'a']—; // 移出窗口

if (i >= m – 1 && Arrays.equals(cntP, cntS)) {
res.add(i – m + 1);
}
}

return res;
}
}

复杂度

· 时间：O(n × 26)，Arrays.equals 每次比较 26 个元素
· 空间：O(1)

对比

解法 时间复杂度 代码简洁度 推荐场景
数组 + diff 优化 O(n + 26) 中等 追求最优，面试展示优化
双指针窗口 O(n) 较简洁 逻辑清晰，通用模式
固定窗口直接比较 O(26n) 最简单 快速实现、数据量小

易错点提醒

相关题目

题目 关系
76. 最小覆盖子串 可变长窗口，同套路
567. 字符串的排列 判断是否存在，思路几乎相同
242. 有效的字母异位词 本题的判定基础
30. 串联所有单词的子串 窗口 + 哈希进阶版