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

古城微笑少年丶 2021-11-19 13:50 227阅读 0赞

**题目**  
给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。  
字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。  
说明：  
字母异位词指字母相同，但排列不同的字符串。  
不考虑答案输出的顺序。  
**示例 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” 的字母异位词。

*来源：力扣（LeetCode）  
链接：[https://leetcode-cn.com/problems/find-all-anagrams-in-a-string][https_leetcode-cn.com_problems_find-all-anagrams-in-a-string]  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*  
**思路**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 1]

*作者：labuladong  
链接：[https://leetcode-cn.com/problems/two-sum/solution/hua-dong-chuang-kou-tong-yong-si-xiang-jie-jue-zi-/][https_leetcode-cn.com_problems_two-sum_solution_hua-dong-chuang-kou-tong-yong-si-xiang-jie-jue-zi-]  
来源：力扣（LeetCode）  
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。*

**代码实现**

package top100;
    
    import java.util.ArrayList;
    import java.util.List;
    
    public class 找到字符串中所有字母异位词 {
        public static void main(String[] args) {
            String s = "cbaebabacd";
            String p ="abc";
            //print(findAnagrams(s,p));
            System.out.println(findAnagrams(s,p));
        }
        public static void print(List[] arr){
            for(int i =0;i<arr.length;i++){
                System.out.print(arr[i]);
            }
        }
        public static List<Integer> findAnagrams(String s, String p) {
            List<Integer> result = new ArrayList<>();
            int[] p_letter = new int[26];
            for (int i = 0; i < p.length(); i++) {//记录p里面的数字分别有几个
                p_letter[p.charAt(i) - 'a']++;
            }
            int start = 0;
            int end = 0;
            int[] between_letter = new int[26];//记录两个指针之间的数字都有几个
            while (end < s.length()) {
                int c = s.charAt(end++) - 'a';//每一次拿到end指针对应的字母
                between_letter[c]++;//让这个字母的数量+1
    
                //如果这个字母的数量比p里面多了,说明这个start坐标需要排除
                while (between_letter[c] > p_letter[c]) {
                    between_letter[s.charAt(start++) - 'a']--;
                }
                if (end - start == p.length()) {
                    result.add(start);
                }
            }
            return result;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 3]

[https_leetcode-cn.com_problems_find-all-anagrams-in-a-string]: https://leetcode-cn.com/problems/find-all-anagrams-in-a-string
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]: /images/20211119/fa9871bdad4f43e4ba842040aaff6af0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 1]: /images/20211119/8afa66d55f684005b499e0ba551d2ac7.png
[https_leetcode-cn.com_problems_two-sum_solution_hua-dong-chuang-kou-tong-yong-si-xiang-jie-jue-zi-]: https://leetcode-cn.com/problems/two-sum/solution/hua-dong-chuang-kou-tong-yong-si-xiang-jie-jue-zi-/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 2]: /images/20211119/85f95d2462a84d0c869cbd85ec27b9fa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 3]: /images/20211119/bbc7d2748ce549889a31531efad40dad.png