【LeetCode】【HOT】438. 找到字符串中所有字母异位词
文章目录
【LeetCode】【HOT】438. 找到字符串中所有字母异位词package hot;import java.util.ArrayList;import java.util.List;public class Solution438 {public static void main(String[] args) {String s = "cbaebabacd";String p = "abc";Solution438 solution = new Solution438();System.out.println(solution.method(s, p));}private List<Integer> method(String s, String p){int n = s.length();int m = p.length();List<Integer> res = new ArrayList<>();int[] cnt = new int[26];for(int i = 0; i < m; i++){cnt[p.charAt(i) - 'a']++;}int a = 0;for(int i : cnt){a += i == 0 ? 0 : 1;}for(int l = 0, r = 0, b = 0; r < n; r++){if(--cnt[s.charAt(r) - 'a'] == 0) b++;if(r - l + 1 > m && ++cnt[s.charAt(l++) - 'a'] == 1) b--;if(b == a) res.add(l);}return res;}}//时间复杂度为 O(n)//空间复杂度为 O(1)
