LeetCode 找到字符串中所有字母异位词【滑动窗口】

╰半橙微兮° 2022-09-11 00:12 121阅读 0赞

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

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

异位词 指字母相同，但排列不同的字符串。

**示例 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" 的异位词。

**提示:**

1 <= s.length, p.length <= 3 * 104
    s 和 p 仅包含小写字母

# 2 解题 #

## 2.1 暴力 ##

public List<Integer> findAnagrams(String s, String p) { 
            List<Integer> rs = new ArrayList<>();
            //统计p出现的次数
            int[] target = new int[26];
            for (int i = 0; i < p.length(); i++) { 
                char c = p.charAt(i);
                target[c - 'a']++;
            }
            //初始化窗口
            int left = 0, right = p.length() - 1;
            //左右指针移动
            while (left <= s.length() - p.length() && right < s.length()) { 
                boolean find = true;
                int[] temp = new int[26];
                //统计
                for (int i = left; i <= right; i++) { 
                    char c = s.charAt(i);
                    temp[c - 'a']++;
                    if (temp[c - 'a'] > target[c - 'a']) { 
                        find = false;
                        break;
                    }
                }
    
                if (find) { 
                    rs.add(left);
                }
                left++;
                right++;
            }
            return rs;
        }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2g5pC656eL5pyI5o-95pif5rKz5Li2_size_19_color_FFFFFF_t_70_g_se_x_16]

## 2.2 滑动窗口 ##

public List<Integer> findAnagrams(String s, String p) { 
            //1 记录
            List<Integer> rs = new ArrayList<>();
            //2 统计目标
            int[] target = new int[26];
            for (int i = 0; i < p.length(); i++) { 
                char c = p.charAt(i);
                target[c - 'a']++;
            }
    
            //3 双指针
            int left = 0, right = 0;
            int[] temp = new int[26];
            while (right < s.length()) { 
                char c = s.charAt(right);
                temp[c - 'a']++;
                while (left <= right && temp[c - 'a'] > target[c - 'a']) { 
                    temp[s.charAt(left) - 'a']--;
                    left++;
                }
    
                if (right - left + 1 == p.length()) { 
                    rs.add(left);
                }
                right++;
            }
    
    
            return rs;
        }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2g5pC656eL5pyI5o-95pif5rKz5Li2_size_20_color_FFFFFF_t_70_g_se_x_16]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2g5pC656eL5pyI5o-95pif5rKz5Li2_size_19_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/02aeb7a049684ee3b7a90f8ff52a1c64.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2g5pC656eL5pyI5o-95pif5rKz5Li2_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/bd0209f3a09a4e2f90f7133288045a00.png