国产亚洲精品久久久,日本aa免费看,操她射她影院,欧美一级在线观看,www.骚,岛国av在线观看网址国产,影音先锋成人在线电影,日韩人妻无码精品综合区

算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選！

今天和大家聊的問題叫做?找到字符串中所有字母異位詞，我們先來看題面：

https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/

Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

給定兩個字符串 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"?的異位詞。

解題

class?Solution?{
????public?List findAnagrams(String s, String p) {
????????char[] arrS = s.toCharArray();
????????char[] arrP = p.toCharArray();
????????
????????// 接收最后返回的結(jié)果
????????List ans = new?ArrayList<>();
????????
????????// 定義一個 needs 數(shù)組來看 arrP 中包含元素的個數(shù)
????????int[] needs = new?int[26];
????????// 定義一個 window 數(shù)組來看滑動窗口中是否有 arrP 中的元素，并記錄出現(xiàn)的個數(shù)
????????int[] window = new?int[26]; 
????????
????????// 先將 arrP 中的元素保存到 needs 數(shù)組中
????????for?(int?i = 0; i < arrP.length; i++) {
????????????needs[arrP[i] - 'a'] += 1;
????????}
????????
????????// 定義滑動窗口的兩端
????????int?left = 0;
????????int?right = 0;
????????
????????// 右窗口開始不斷向右移動
????????while?(right < arrS.length) {
????????????int?curR = arrS[right] - 'a';
????????????right++;
????????????// 將右窗口當前訪問到的元素 curR 個數(shù)加 1 
????????????window[curR] += 1;
????????????
????????????// 當 window 數(shù)組中 curR 比 needs 數(shù)組中對應(yīng)元素的個數(shù)要多的時候就該移動左窗口指針 
????????????while?(window[curR] > needs[curR]) {
????????????????int?curL = arrS[left] - 'a';
????????????????left++;
????????????????// 將左窗口當前訪問到的元素 curL 個數(shù)減 1 
????????????????window[curL] -= 1; 
????????????}
????????????
????????????// 這里將所有符合要求的左窗口索引放入到了接收結(jié)果的 List 中
????????????if?(right - left == arrP.length) {
????????????????ans.add(left);
????????????}
????????}
????????return?ans;
????}
}