數組男图、雙指針杜秸、滑動窗口、夾逼么介、前綴數組

三數之和

給你一個包含 n 個整數的數組 nums，判斷 nums 中是否存在三個元素 a府怯，b刻诊，c ，使得 a + b + c = 0 牺丙？請你找出所有滿足條件且不重復的三元組则涯。
注意：答案中不可以包含重復的三元組。

示例：
給定數組 nums = [-1, 0, 1, 2, -1, -4]，
滿足要求的三元組集合為：
[[-1, 0, 1],[-1, -1, 2]]

解法一：排序+夾逼（推薦）
1）首先對數組進行排序（涉及數的大小一般都會進行排序處理）粟判，有助于去重的實現(xiàn)肖揣；
2）排序后固定一個數 nums[i]，再使用左右指針浮入，對后面的數組進行夾逼遍歷（nums[L]和nums[R]）龙优，計算三個數的和 sum 判斷是否滿足為 0，滿足則添加進結果集
3）如果 nums[i]大于 0事秀，則三數之和必然無法等于 0彤断，結束循環(huán)；
如果 nums[i] == nums[i-1]易迹，則說明該數字重復宰衙，會導致結果重復，所以應該跳過睹欲；
當 sum == 0 時供炼，nums[L] == nums[L+1]則會導致結果重復，應該跳過窘疮，L++袋哼；
當 sum == 0時，nums[R] == nums[R-1] 則會導致結果重復闸衫，應該跳過涛贯，R--；

時間復雜度： $O(n^2 )$ 蔚出，n 為數組長度

public static List<List<Integer>> threeSum2(int[] nums) {
        List<List<Integer>> ans = new ArrayList();
        int len = nums.length;
        if (nums == null || len < 3) {
            return ans;
        }
        Arrays.sort(nums); // 排序
        for (int i = 0; i < len; i++) {
            if (nums[i] > 0) {
                break; // 如果當前數字大于0弟翘，則三數之和一定大于0，所以結束循環(huán)
            }
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue; // 去重
            }
            int L = i + 1;
            int R = len - 1;
            while (L < R) {
                int sum = nums[i] + nums[L] + nums[R];
                if (sum == 0) {
                    ans.add(Arrays.asList(nums[i], nums[L], nums[R]));
                    while (L < R && nums[L] == nums[L + 1]) L++; // 去重
                    while (L < R && nums[R] == nums[R - 1]) R--; // 去重
                    L++;
                    R--;
                } else if (sum < 0){
                    L++;
                } else if (sum > 0) {
                    R--;
                }
            }
        }
        return ans;
    }

解法二：二重暴力+Hash（Slow）
1）暴力解法為三重for循環(huán)遍歷所有情況骄酗，考慮到第三個數可以由前兩個數得到稀余，使用HashMap可以避免第三重循環(huán)，從而達到 $O(n^2)$ 復雜度
2）用Set<List<Integer>>去重趋翻，前提是list里的元素的順序一致睛琳；

private List<List<Integer>> hashSolution(int[] nums) {
       if (nums == null || nums.length <= 2) {
            return Collections.emptyList();
        }
        Set<List<Integer>> results = new LinkedHashSet<>();

        for (int i = 0; i < nums.length - 2; i++) {
            Set<Integer> hashSet = new HashSet<>();
            for (int j = i + 1; j < nums.length; j++) {
                int d = -nums[i] - nums[j];
                if (hashSet.contains(d)) {
                    List<Integer> list = Arrays.asList(nums[i], d, nums[j]);
                    //  排序, 否則三個相同的數, 但位置不同, 無法去重
                    list.sort(Comparator.naturalOrder());
                    results.add(list);
                } else {
                    hashSet.add(nums[j]);
                }
            }
        }
        return new ArrayList<>(results);
    }

四數之和

雙指針
1）注意去重的代碼
2）剪枝可節(jié)省時間

    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        int n = nums.length;
        Arrays.sort(nums);
        for (int i = 0; i <= n - 4; i++) {
            // 去重
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            // 剪枝
            if(nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target){
                return ans;
            }
            if(nums[n-1] + nums[n-2] + nums[n-3] + nums[n - 4] < target){
                return ans;
            }
            for (int j = i + 1; j <= n - 3; j++) {
                // 去重
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                // 剪枝
                if(nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target){
                    continue;
                }
                if(nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target){
                    continue;
                }
                int left = j + 1;
                int right = n - 1;
                while (left < right) {
                    // 去重
                    while (left < right && left > j + 1 && nums[left] == nums[left - 1]) {
                        left++;
                    }
                    while (left < right && right < n - 1 && nums[right] == nums[right + 1]) {
                        right--;
                    }
                    if(left < right){
                        int sum = nums[i] + nums[j] + nums[left] + nums[right];
                        if (sum == target) {
                            ans.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                            left++;
                            right--;
                        } else if (sum > target) {
                            right--;
                        } else {
                            left++;
                        }
                    }
                }
            }
        }
        return ans;
    }

和為k的子數組

給定一個整數數組和一個整數 k，你需要找到該數組中和為 k 的連續(xù)的子數組的個數嘿歌。
示例 1 :
輸入:nums = [1,1,1], k = 2
輸出: 2 , [1,1] 與 [1,1] 為兩種不同的情況掸掏。

解法一：滑動窗口
1）先固定一個數nums[start]茁影，然后移動另一個指針宙帝，求和即可
2）依次移動固定數的位置，重復上述過程
兩個指針募闲，兩輪遍歷步脓，算法復雜度為 $O(N^2)$

class Solution {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length;
        int count = 0;

        int lastSum = 0;
        for (int start = 0; start < n; start++) {
            for (int end = start; end < n; end++) {
               if(end == start){
                   if(nums[start] == k){
                       count ++;
                   }
                   lastSum = nums[end];
               }else {
                   lastSum += nums[end];
                   if(lastSum == k){
                       count ++;
                   }
               }
            }
        }

        return count;
    }
}

解法二：HashMap+前綴和（推薦）
1）考慮到此題只需給出滿足條件的子序列的數量，而不需要具體的子序列：可使用一個map記錄所有從0開始的子序列的sum值及其出現(xiàn)次數，通過長序列的sum減去短序列的sum可以得到中間子序列的sum值靴患，所以就不需要兩個指針了仍侥。
2）建立map表用于存儲每個從零項開始的連續(xù)子數組的sum求和及其出現(xiàn)的次數，初始化為（0,1）鸳君，表示和為0的連續(xù)子數組（空數組）出現(xiàn)1次农渊。
3）sum的值是在對nums數組的遍歷中不斷累加當前元素的，res的值則需要查找map中是否已存在sum-k的元素或颊，也就是在查找此前所有從0項開始累加的連續(xù)子項和中有沒有sum-k砸紊。因為： $長序列sum-短序列sum=sum-(sum-k)=k$ 如果有的話，則說明從該項到當前項的連續(xù)子數組和必定為k囱挑，那么res則可以和這個sum的對應值醉顽，即這個sum出現(xiàn)的次數，相加得到新的res平挑。
算法復雜度為O(N)游添。

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        int sum = 0, ret = 0;       
        // sum為0的子序列出現(xiàn)一次，即空序列通熄；
        map.put(0, 1);

        for(int i = 0; i < nums.length; ++i) {
            sum += nums[i];
            if(map.containsKey(sum-k))
                ret += map.get(sum-k);
            map.put(sum, map.getOrDefault(sum, 0)+1);
        }
        
        return ret;
    }
}

和可被 K 整除的子數組

給定一個整數數組 A唆涝，返回其中元素之和可被 K 整除的（連續(xù)、非空）子數組的數目唇辨。
示例：
輸入：A = [4,5,0,-2,-3,1], K = 5
輸出：7
解釋：
有 7 個子數組滿足其元素之和可被 K = 5 整除：
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]
提示：
1 <= A.length <= 30000
-10000 <= A[i] <= 10000
2 <= K <= 10000

解法:前綴和+同余定理
1）通常涉及連續(xù)子數組的時候石抡，可以使用前綴和來解決。連續(xù)子數組的求和助泽，可以使用前綴和的差來得到啰扛。前綴和： $Sum(i)=num[0] + num[1] + ... + num[i]$ ，任意連續(xù)子數組的求和： $Sum(i,j)=Sum(j) - Sum(i-1)$ 嗡贺。
2）同余定理： $Sum(i,j)\%K=0$ 即 $(Sum(j) - Sum(i-1))\%K=0$ 隐解，根據同余定理得到： $Sum(j)\%K=Sum(i-1)\%K$ 。
3）根據上面的結論诫睬，我們使用一個數組記錄前綴和對K取模的結果的數量煞茫。即取模結果為0~K-1的各個值的數量。假設對K取模值為r的前綴和共有n個摄凡，那么這n個前綴和中任意取2個续徽，即得到一個滿足條件的子數組，所以這種情況下亲澡，共有 $C_{n}^{2}=\frac{n*(n-1)}{2}$ 個滿足條件的子數組钦扭。將所有的取模值r，計算求和即可得到最后的解床绪。注意：對于取模值r為0的情況客情，比較特殊其弊，除了任選兩個前綴和的組合情況之外, 每個前綴和本身就是一個滿足條件的子數組，所以假設有n個取模值r為0的前綴和膀斋，對應情況的子數組個數為： $n+C_{n}^{2}$ 梭伐。

 public static int subarraysDivByK(int[] A, int K) {
        int ret = 0;

        int[] counts = new int[K];

        // 前綴和
        int sum = 0;
        for (int i = 0; i < A.length; i++) {
            sum += A[i];
            // 保證對K取模的結果都為正數0~K-1, Java中-2%6=-2, 我們希望的值是-2%6=4
            int mod = sum % K;
            if(mod < 0){
                mod += K;
            }
            counts[mod] += 1;
        }

        for (int i = 0; i < K; i++) {
            int count = counts[i];
            if (i == 0) {
                ret += count + count * (count - 1) / 2;
            } else {
                ret += count * (count - 1) / 2;
            }
        }

        return ret;
    }

無重復字符的最長子串

給定一個字符串，請你找出其中不含有重復字符的最長子串的長度仰担。

示例 1:
輸入: "abcabcbb"
輸出: 3
解釋: 因為無重復字符的最長子串是 "abc"糊识，所以其長度為 3。
示例 2:
輸入: "bbbbb"
輸出: 1
解釋: 因為無重復字符的最長子串是 "b"摔蓝，所以其長度為 1技掏。
示例 3:
輸入: "pwwkew"
輸出: 3
解釋: 因為無重復字符的最長子串是 "wke"，所以其長度為 3项鬼。

滑動窗口
依次遞增地枚舉子串的起始位置哑梳，那么子串的結束位置也是遞增的！這里的原因在于绘盟，假設我們選擇字符串中的第 k個字符作為起始位置鸠真，并且得到了不包含重復字符的最長子串的結束位置為 rk。那么當我們選擇第 k+1 個字符作為起始位置時龄毡，首先從 k+1 到 rk的字符顯然是不重復的吠卷，并且由于少了原本的第 k 個字符，我們可以嘗試繼續(xù)增大 rk 沦零，直到右側出現(xiàn)了重復字符為止祭隔。

這樣以來，我們就可以使用「滑動窗口」來解決這個問題了：

我們使用兩個指針表示字符串中的某個子串（的左右邊界）路操。其中左指針代表著上文中「枚舉子串的起始位置」疾渴，而右指針即為上文中的 rk；

在每一步的操作中屯仗，我們會將左指針向右移動一格搞坝，表示我們開始枚舉下一個字符作為起始位置，然后我們可以不斷地向右移動右指針魁袜，但需要保證這兩個指針對應的子串中沒有重復的字符桩撮。在移動結束后，這個子串就對應著以左指針開始的峰弹，不包含重復字符的最長子串店量。我們記錄下這個子串的長度；在枚舉結束后鞠呈，我們找到的最長的子串的長度即為答案融师。

 public static int lengthOfLongestSubstring2(String s) {

        int n = s.length();
        if (n <= 1) {
            return n;
        }
        int maxLen = 1;
        Set<Character> chars = new HashSet<>();

        int R = 0;
        for(int L = 0; L<n; L++){
            if(L > 0){
                chars.remove(s.charAt(L-1));
            }

            while (R < n && !chars.contains(s.charAt(R))){
                chars.add(s.charAt(R));
                R++;
            }

            maxLen = Math.max(maxLen, R-L);
        }

        return maxLen;
    }

或者事實上L每次不止可以加1

public static int lengthOfLongestSubstring(String s) {

        int n = s.length();
        if (n <= 1) {
            return n;
        }

        int maxLen = 1;
        Set<Character> chars = new HashSet<>();

        int L = 0;
        int R = 0;
        while (L < n && R < n){
            char c = s.charAt(R);
            if(chars.contains(c)){
                maxLen = Math.max(maxLen, R-L);
                while (s.charAt(L) != c){
                    chars.remove(s.charAt(L));
                    L++;
                }
                L++;
            }
            chars.add(c);
            R++;
        }

        maxLen = Math.max(maxLen, R-L);

        return maxLen;

    }

數組中重復的數據(https://leetcode-cn.com/problems/find-all-duplicates-in-an-array/)

給定一個整數數組 a，其中1 ≤ a[i] ≤ n （n為數組長度）, 其中有些元素出現(xiàn)兩次而其他元素出現(xiàn)一次粟按。
找到所有出現(xiàn)兩次的元素诬滩。
你可以不用到任何額外空間并在O(n)時間復雜度內解決這個問題嗎霹粥？
示例：
輸入:
[4,3,2,7,8,2,3,1]
輸出:
[2,3]

利用索引號+取反
利用索引號灭将，因為所有數值是在1~n之間疼鸟，那么我們可以用索引0表示數字1，索引1表示數字2...庙曙。每遍歷一次數組空镜，就將此數的index對應的原來正的數字取負，若此index對應的數為負捌朴，則說明已出現(xiàn)過吴攒；并且取負之后仍然可以取到正確的位置值（取絕對值即可）。

public static List<Integer> findDuplicates(int[] nums) {

        List<Integer> ans = new ArrayList<>();

        for (int num : nums){
            int index = Math.abs(num)-1;
            if(nums[index] < 0){
                ans.add(Math.abs(num));
            }
            nums[index] = -nums[index];
        }

        return ans;
    }

最長湍流子數組

當 A 的子數組 A[i], A[i+1], ..., A[j] 滿足下列條件時砂蔽，我們稱其為湍流子數組：
若 i <= k < j洼怔，當 k 為奇數時， A[k] > A[k+1]左驾，且當 k 為偶數時镣隶，A[k] < A[k+1]；
或若 i <= k < j诡右，當 k 為偶數時安岂，A[k] > A[k+1] ，且當 k 為奇數時帆吻， A[k] < A[k+1]域那。
也就是說，如果比較符號在子數組中的每個相鄰元素對之間翻轉猜煮，則該子數組是湍流子數組次员。
返回 A 的最大湍流子數組的長度。

示例 1：
輸入：[9,4,2,10,7,8,8,1,9]
輸出：5
解釋：(A[1] > A[2] < A[3] > A[4] < A[5])
示例 2：
輸入：[4,8,12,16]
輸出：2
示例 3：
輸入：[100]
輸出：1

滑動窗口

public static int maxTurbulenceSize(int[] A) {

        if (A.length <= 1) {
            return A.length;
        }

        int ans = 1;
        int start = 0;
        for(int i=1; i<A.length; i++){
            int c = Integer.compare(A[i-1], A[i]);
            if(i == A.length-1 || c * Integer.compare(A[i], A[i+1]) != -1){
                if(c != 0){ // 避免所有數都一樣時, 答案不為1
                    ans = Math.max(ans, i-start+1);
                }
                start = i;
            }
        }

        return ans;
    }

替換后的最長重復字符(https://leetcode-cn.com/problems/longest-repeating-character-replacement/)

給你一個僅由大寫英文字母組成的字符串王带，你可以將任意位置上的字符替換成另外的字符翠肘，總共可最多替換 k 次。在執(zhí)行上述操作后辫秧，找到包含重復字母的最長子串的長度束倍。
注意:
字符串長度和 k 不會超過 104。
示例 1:
輸入:
s = "ABAB", k = 2
輸出:
4
解釋:
用兩個'A'替換為兩個'B',反之亦然盟戏。
示例 2:
輸入:
s = "AABABBA", k = 1
輸出:
4
解釋:
將中間的一個'A'替換為'B',字符串變?yōu)?"AABBBBA"绪妹。
子串 "BBBB" 有最長重復字母, 答案為 4。

滑動窗口
本題是比較典型的滑動窗口問題

這類問題一般通過一個滑動窗口就能在O(N)的時間復雜度下求解

本題可以先退化成考慮K=0的情況柿究，此時題目就變成了求解字符串中最長連續(xù)子串長度問題了

我們先可以通過這個特例先了解一下滑動窗口的求解過程

上圖的求解過程展示中邮旷，窗口從左至右不斷擴張/滑動，當窗口觸達字符串末尾字符時蝇摸，運算結束婶肩，窗口的寬度為最終結果办陷。初始窗口的寬度為1，我們不斷的通過向當前窗口覆蓋的子串后面追加一個字符看是否能滿足我們的要求律歼，如果滿足窗口擴張民镜，如果不滿足，窗口向右滑動险毁。

當K>0時制圈，子串的條件變成了允許我們變換子串中的K個字符使其變成一個連續(xù)子串

那么這個題的關鍵點就是我們如何判斷一個字符串改變K個字符，能夠變成一個連續(xù)串

如果當前字符串中的出現(xiàn)次數最多的字母個數 + K >= 串長度畔况，那么這個串就是滿足條件的

我們維護一個數組int[26]來存儲當前窗口中各個字母的出現(xiàn)次數鲸鹦，left表示窗口的左邊界，right表示窗口右邊界

窗口擴張：left不變跷跪，right++
窗口滑動：left++, right++

public static int characterReplacement(String s, int k) {

        int n = s.length();
        if (n <= 1 || n <= k + 1) {
            return n;
        }

        int[] charCount = new int[26];
        int L = 0;
        int R = 0;
        charCount[s.charAt(R) - 'A']++;
        int maxCount = 1;

        while (R < n) {

            if(maxCount + k >= R - L + 1){
                // 窗口擴大
                R++;
                if (R < n) {
                    int index = s.charAt(R) - 'A';
                    charCount[index]++;
                    maxCount = Math.max(maxCount, charCount[index]);
                }

            }else {
                // 窗口移動
                charCount[s.charAt(L) - 'A']--;
                L++;

                R++;
                if (R < n) {
                    int index = s.charAt(R) - 'A';
                    charCount[index]++;
                    maxCount = Math.max(maxCount, charCount[index]);// 真實值 <= 這里的值, 不過不影響結果的正確性
                }
            }
        }

        return R - L;
    }

上述代碼可以簡化為

public static int characterReplacement(String s, int k) {

        int n = s.length();
        if (n <= 1 || n <= k + 1) {
            return n;
        }

        int[] charCount = new int[26];
        int L = 0;
        int R = 0;
        charCount[s.charAt(R) - 'A']++;
        int maxCount = 1;

        while (R < n) {
            // 窗口移動
            if(maxCount + k < R - L + 1){
                charCount[s.charAt(L) - 'A']--;
                L++;
            }

            // 窗口擴大
            R++;
            if (R < n) {
                int index = s.charAt(R) - 'A';
                charCount[index]++;
                maxCount = Math.max(maxCount, charCount[index]);
            }
        }

        return R - L;
    }

16. 最接近的三數之和](https://leetcode-cn.com/problems/3sum-closest/)

給定一個包括 n 個整數的數組 nums和一個目標值 target馋嗜。找出 nums中的三個整數，使得它們的和與 target 最接近吵瞻。返回這三個數的和葛菇。假定每組輸入只存在唯一答案。

示例：
輸入：nums = [-1,2,1,-4], target = 1
輸出：2
解釋：與 target 最接近的和是 2 (-1 + 2 + 1 = 2) 听皿。

提示：

3 <= nums.length <= 10^3
-10^3 <= nums[i] <= 10^3
-10^4 <= target <= 10^4

雙指針

public static int threeSumClosest(int[] nums, int target) {

        Arrays.sort(nums);

        int ans = nums[0] + nums[1] + nums[2];
        for(int fix = 0; fix < nums.length; fix ++){
            int L = fix + 1;
            int R = nums.length - 1;
            while (L < R){
                int sum = nums[fix] + nums[L] + nums[R];
                if(Math.abs(sum - target) < Math.abs(ans - target)){
                    ans = sum;
                }
                if(sum - target > 0){
                    R--;
                }else if(sum == target){
                    return target;
                }else {
                    L++;
                }
            }
        }
        return ans;
    }

長度最小的子數組

雙指針（滑動伸縮窗口）
技巧總結：
1）求連續(xù)子數組長度熟呛，自然聯(lián)想到雙指針；
2）涉及連續(xù)子數組的和尉姨，可以聯(lián)想到前綴數組（暴力解法中才會用到庵朝，雙指針解法中不用）;
3）雙指針的實現(xiàn)：兩個指針+while循環(huán)。（或者for循環(huán)中嵌套while循環(huán)）
時間復雜度為O(n)又厉，因為每個元素最多遍歷兩遍九府，左指針一遍，右指針一遍覆致。

public int minSubArrayLen(int s, int[] nums) {
        int n = nums.length;
        if(n == 0){
            return 0;
        }
        int minLen = 0;
        int L = 0;
        int R = 0;
        int sum = nums[R];
        while (L <= R && R < n){
            if(sum >= s){
                int len = R - L + 1;
                minLen = minLen == 0 ? len : Math.min(len, minLen);
                sum -= nums[L++];
            }else{
                R ++;
                if(R < n){
                    sum += nums[R];
                }
            }
        }
        return minLen;
    }

顏色分類

計數排序

    public void sortColors(int[] nums) {
        int[] count = new int[3];
        for(int num : nums){
            count[num] ++;
        }
        int index = 0;
        for(int i=0; i<count.length; i++){
            while (count[i]-- > 0){
                nums[index++] = i;
            }
        }
    }

多指針

curr指針侄旬，遍歷數組，將0元素放在最左邊煌妈，將2元素放在最右邊儡羔，1元素繼續(xù)；通過交換元素操作璧诵；
p0指針汰蜘，指向左邊0元素的最右邊界；
p2指針之宿，指向右邊2元素的最左邊界族操；

    public void sortColors(int[] nums) {
        int curr = 0;
        int p0 = 0;
        int p2 = nums.length-1;
        while (curr < p2){
            if(nums[curr] == 0){
                swap(nums, p0, curr);
                p0 ++;
                curr++;
            }else if(nums[curr] == 1){
                curr++;
            }else {
                swap(nums, p2, curr);
                p2--;
            }
        }
    }

    public void swap(int[] nums, int index1, int index2){
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }

字符串的排列

數組匹配

我們可以使用數組來存儲各字符的出現(xiàn)頻率，然后判斷兩個數組是否相等來判斷兩個長度相同的字符串是否互為排列比被。給定字符串僅包含小寫字母（'a'到'z'）色难。因此我們需要采用大小為 26 的數組泼舱。

    public boolean checkInclusion(String s1, String s2) {
        int len = s1.length();
        int[] count1 = getCount(s1);
        for (int i = 0; i <= s2.length() - len; i++) {
            String sub = s2.substring(i, i + len);
            if (match(count1, getCount(sub))) {
                return true;
            }
        }
        return false;
    }

    public int[] getCount(String s) {
        int[] count = new int[26];
        for (char c : s.toCharArray()) {
            count[c - 'a']++;
        }
        return count;
    }

    public boolean match(int[] count1, int[] count2) {
        for (int i = 0; i < 26; i++) {
            if (count1[i] != count2[i]) {
                return false;
            }
        }
        return true;
    }

滑動窗口優(yōu)化

在上述的過程中，在對s2進行滑動的時候枷莉，都重新計算了子串的計數數組娇昙，其實沒有必要，因為相鄰的數組之間只有微笑的區(qū)別依沮，只需要計算第一個窗口的計數數組涯贞，后面每移動一步枪狂，做出相應改變即可危喉。

    public boolean checkInclusion(String s1, String s2) {
        int len = s1.length();
        int[] count1 = getCount(s1);
        if (s2.length() < s1.length()) {
            return false;
        }
        int[] count2 = getCount(s2.substring(0, len));
        if (match(count1, count2)) {
            return true;
        }
        for (int i = 1; i <= s2.length() - len; i++) {
            count2[s2.charAt(i - 1) - 'a']--;
            count2[s2.charAt(i + len - 1) - 'a']++;
            if (match(count1, count2)) {
                return true;
            }
        }
        return false;
    }

    public int[] getCount(String s) {
        int[] count = new int[26];
        for (char c : s.toCharArray()) {
            count[c - 'a']++;
        }
        return count;
    }

    public boolean match(int[] count1, int[] count2) {
        for (int i = 0; i < 26; i++) {
            if (count1[i] != count2[i]) {
                return false;
            }
        }
        return true;
    }

字母異位詞分組

跟上題類似

將count數組映射成一個字符串key：用"#"連接所有數字即可。

    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> ans = new ArrayList<>();
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            int[] count = getCount(str);
            String countKey = getCountKey(count);
            if(map.containsKey(countKey)){
                map.get(countKey).add(str);
            }else {
                List<String> list = new ArrayList<>();
                list.add(str);
                map.put(countKey, list);
            }
        }
        for(List<String> list : map.values()){
            ans.add(list);
        }
        return ans;
    }

    public String getCountKey(int[] count) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 26; i++) {
            sb.append("#").append(count[i]);
        }
        return sb.toString();
    }

    public int[] getCount(String s) {
        int[] count = new int[26];
        for (char c : s.toCharArray()) {
            count[c - 'a']++;
        }
        return count;
    }

數組洪囤、雙指針徒坡、滑動窗口、夾逼瘤缩、前綴數組

數組喇完、雙指針、滑動窗口剥啤、夾逼锦溪、前綴數組