海淀团队组建网站_网络编程技术及应用_seo排名赚能赚钱吗_视频号怎么付费推广

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

题目描述

给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
输入: s = “cbaebabacd”, p = “abc”
输出: [0,6]
解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。

思路

滑动窗口

1. 定义一个数组int[] cnt = new int[26]; 表示26个字母
2. for循环遍历字符串p，cnt[p.charAt(i)-‘a’]++;
3. 定义滑动窗口两个指针l=0; r=0;
4. for循环遍历字符串s，cnt[p.charAt(i)-‘a’]--;
   I. 当出现字母<0的情况，说明此时窗口内可能出现了p不需要的字母，或者是出现了>p所需的字母数量，可以进行窗口的收缩
   II. 使用while循环做窗口收缩，while(cnt[p.charAt(i)-‘a’]<0)时，cnt[s.charAt(l)-‘a’]++; l++;
   III. 收缩停止后，对窗口情况进行检查，若(r-l+1==p.length())，则将索引加入到结果集中
5. 我的QA：
   Q：会不会出现r-l+1==p.length()且cnt中仍有必要元素>0的情况？
   A：不会，不断满足条件的情况下代码会统计满足要求的结果，当出现非必要元素时窗口会发生收缩，以排除掉不属于需求窗口的元素。可以考虑两个例子：s=”abcab”,t=”ab”和s=”acbab”,t=”ab”就知道了

代码

class Solution {public List<Integer> findAnagrams(String s, String p) {// 滑动窗口解法int[] cnt = new int[26];for (int i = 0; i < p.length(); i++) {cnt[p.charAt(i) - 'a']++;}List<Integer> result = new ArrayList<>();int l = 0, r = 0;for (; r < s.length(); r++) {cnt[s.charAt(r) - 'a']--;// ==0说明此时s窗口内的字母数量和p完全契合// <0说明s窗口内的“要求”字母数量已经>p的了，可以移动l来收缩窗口while (cnt[s.charAt(r) - 'a'] < 0){cnt[s.charAt(l) - 'a']++;l++;}// 检查窗口情况，是不是满足要求，满足则将结果放入resultif (r - l + 1 == p.length()) {result.add(l);}}return result;}
}