本文共 1156 字，大约阅读时间需要 3 分钟。

给定一个字符串 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” 的字母异位词。

解题思路：

对p串的每个字符进行hash计数。

从下标0开始遍历字符串s，对于每个下标，判断接下来长度为pLength的子串是否为目标串的字母异位词；

判断过程为临时拷贝一份新的技术数组，然后遍历到的子串的每个字符的计数器减1，出现负数则break结束当前子串的统计，进入下一个子串的统计；

如果统计了长度为pLength的子串扔没有发现计数器减为负数的情况，说明找到了一个符合条件的字母异位词，把子串的第一个字符下标存下来。

class Solution {
   	    public List
   
     findAnagrams(String s, String p) {
   	    		    	// 对p串进行hash计数	    	int pLength = p.length();	    	int sLength = s.length();	    		    	int[] counts = new int[26];	    	for(int i=0;i
    
      res = new ArrayList<>();	    		    	// 从下标0开始遍历字符串	    	for(int i=0;i<=sLength-pLength;i++) {
   	    		//找到临时数组	    		int[] tempCounts = Arrays.copyOf(counts,26);	    		int j = i;	    		for(;j
     
      
       =pLength+i) {
   	    			res.add(i);	    		}	    	}	    	return res;	    }	}
      
     
    
   

转载地址：https://codingchaozhang.blog.csdn.net/article/details/111424612 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！