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

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

• 题目描述
• 示例
• 思路
• 解题方法
• 复杂度
• Coindex.php/tags-41973.html" >de

  滑动窗口+优化判断解法（Java 执行用时：4ms，击败98.73%）

  题目描述

  示例

  思路

  1. 在字符串 s s s中查找字符串 p p p的字母异位词，所以滑动窗口大小固定为 p p p的长度。
  2. 用 int[26] 记录 p p p的字母个数与滑动窗口中字母个数的状态，int diff表示滑动窗口中词与字符串 p p p的差异，值最大为字符串 p p p的长度。

  解题方法

  1. m m m = 字符串sss的长度， n n n = 字符串 p p p的长度， r e s res res是返回结果的列表
  2. 如果 m m m小于 n n n，则返回空列表。
  3. 首先，用 int[26] 记录字符串 p p p中字母的数量，每遇到一个字母就在数组中对应位置减 1 1 1。
  4. 设滑动窗口初始位置， l e f t = 0 left=0 left=0， l = n − 1 l=n−1 l=n−1，将窗口中字符记录入数组中，每遇到一个字母就在对应位置加 1 1 1，如果某一个位置的值大于 0 0 0，说明统计的这个字符是多余的，diff加 1 1 1。最终，如果 d i f f = 0 diff=0 diff=0，则 l e f t = 0 left=0 left=0是一个满足条件的位置，加入 r e s res res。
  5. 滑动窗口的左边界向右移动， l e f t + = 1 left+=1 left+=1，删除掉 l e f t − 1 left−1 left−1位置的字符，加入 l e f t + l left+l left+l位置的字符。从数组中删除 l e f t − 1 left−1 left−1位置的字符后，如果数组中对应位置的值小于 0 0 0，说明与字符串 p p p相比，缺失了对应位置的字符，所以 d i f f diff diff加 1 1 1。
  6. 判断 d i f f = = 0 diff==0 diff==0，如果等于 0 0 0，则该窗口满足条件，将 l e f t left left加入 r e s res res。

  复杂度

  1. 时间复杂度： O ( n + m + Σ ) O(n+m+Σ) O(n+m+Σ)
  2. 空间复杂度： O ( Σ ) O(Σ) O(Σ)

  Code

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