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

一、题目

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

二、题解

思路： 固定长度的滑动窗口 + 频次数组。

  • 异位词的本质是字符种类与数量完全相同，因此用两个长度为 26 的数组 sCount、pCount 分别记录窗口内字符频次与目标串 p 的字符频次。
  • 先初始化第一个窗口（前 pLen 个字符），比较两个频次数组是否相等。
  • 之后窗口每右移一格：移出左边界字符（对应频次 -1），加入右边界新字符（对应频次 +1），再比较两数组是否相等，相等则记录起始索引。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int sLen = s.length(), pLen = p.length();

        // 边界条件：如果目标字符串 p 比 源字符串 s 还要长，那 s 中肯定不存在 p 的异位词
        if (sLen < pLen) {
            return new ArrayList<>();
        }

        List<Integer> ans = new ArrayList<>();

        // 创建两个长度为 26 的数组，充当“记账本”
        // sCount 记录当前滑动窗口内，每个字母出现的次数
        // pCount 记录目标字符串 p 中，每个字母出现的次数
        int[] sCount = new int[26];
        int[] pCount = new int[26];

        // 1. 初始化阶段：构建目标频次数组 pCount，以及 s 中的【第一个窗口】
        for (int i = 0; i < pLen; i++) {
            // 记录 s 中前 pLen 个字符的频次（第一个窗口）
            ++sCount[s.charAt(i) - 'a'];
            //统计目标字符串 p 的字符
            ++pCount[p.charAt(i) - 'a'];
        }

        // 检查刚刚构建的【第一个窗口】是否正好是一个字母异位词
        // 如果频次数组完全相等，说明找到了一个异位词，其起始索引为 0
        if (Arrays.equals(sCount, pCount)) {
            ans.add(0);
        }

        // 2. 窗口滑动阶段：窗口大小固定为 pLen，开始向右滑动
        // i 代表要被移出窗口的那个字符的索引
        // i + pLen 代表要被新加入窗口的那个字符的索引
        for (int i = 0; i < sLen - pLen; ++i) {
            // 窗口整体向右移动一格：

            // 步骤 A：把左边界移出窗口的字符，在 sCount 频次中减 1
            --sCount[s.charAt(i) - 'a'];

            // 步骤 B：把右边界新进入窗口的字符，在 sCount 频次中加 1
            ++sCount[s.charAt(i + pLen) - 'a'];

            // 检查滑动后的新窗口，其内部的字符频次是否和目标 pCount 一致
            if (Arrays.equals(sCount, pCount)) {
                // 如果一致，记录当前窗口的起始索引。
                // 因为移出窗口的字符索引是 i，所以新窗口的起始索引是 i + 1
                ans.add(i + 1);
            }
        }

        return ans;
    }
}

时间复杂度：O(n+26×(n−m))O(n + 26 \times (n - m))，即 O(n)O(n)（nn 为 s 长度，mm 为 p 长度，每次窗口滑动用 Arrays.equals 比较 26 个元素）

空间复杂度：O(26)O(26)，即 O(1)O(1)（两个固定大小的频次数组，结果数组不计入）

评论