Leetcode 209題： 長(zhǎng)度最小的子數(shù)組

給定一個(gè)含有 n 個(gè)正整數(shù)的數(shù)組和一個(gè)正整數(shù) s 拌倍，找出該數(shù)組中滿足其和 ≥ s 的長(zhǎng)度最小的連續(xù)子數(shù)組箱季，并返回其長(zhǎng)度涯穷。如果不存在符合條件的連續(xù)子數(shù)組，返回 0藏雏。

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/minimum-size-subarray-sum
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有拷况。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

這種連續(xù)子數(shù)組的問(wèn)題赚瘦，暴力解法粟誓，也就是列出所有的子數(shù)組來(lái)進(jìn)行求和，再一一比對(duì)起意，符合要求的存儲(chǔ)子數(shù)組的長(zhǎng)度鹰服，最后輸出最小的長(zhǎng)度，這會(huì)導(dǎo)致O(n^3)的復(fù)雜度揽咕。

 public int minSubArrayLen(int s, int[] nums) {
        int len = nums.length;
        int res = len + 1;
        for(int l = 0; l < len; l ++){
            for(int r = l; r < len; r ++){
                int sum = 0;
                for(int i = l; i <= r; i ++){
                    //如果要查看子數(shù)組的序列获诈，可打印i
                    //System.out.print(i+"-");
                    sum += nums[i];
                    if(sum >= s)
                        res = Math.min(res, r - l + 1);
                }
                //System.out.printl();
            }
        }
        
        if(res == len + 1)
            return 0;
        return res;
    }

使用滑動(dòng)窗口，可以將復(fù)雜度下降至O(n)心褐，其中兩個(gè)指針l與r切诀，分別指向窗口的左右邊界微王，當(dāng)窗口內(nèi)數(shù)值的和大于s時(shí)，左邊界往前移，去除最左邊的數(shù)值淮摔，如果小于s時(shí)，則右邊界往前配深，新增加一個(gè)數(shù)值鹏漆。

public int minSubArrayLen(int s, int[] nums) {
        int len = nums.length;

        int l = 0, r = -1;
        int sum = 0;
        int res = len + 1;
        while (l < len){

            if(r + 1 < len && sum < s)
                sum  += nums[++r];
            else
                sum -= nums[l++];

            if(sum >= s)
                res = Math.min(res, r-l+1);
        }

        if(res == len + 1)
            return  0;

        return res;
    }

Leetcode 3題： 無(wú)重復(fù)字符的最長(zhǎng)字串

這里使用了一個(gè)小技巧：每一次一個(gè)新的字符再加入子串時(shí)，都需要判斷一下這個(gè)字符是否已經(jīng)出現(xiàn)過(guò)袍睡，可以使用一個(gè)新的數(shù)字知染，它的索引對(duì)應(yīng)字符的ASCII碼，這里也可以同時(shí)處理大小寫不敏感的問(wèn)題斑胜。
當(dāng)這個(gè)索引對(duì)應(yīng)的值為0時(shí)控淡，就說(shuō)明未出現(xiàn)過(guò)，為1時(shí)止潘，就說(shuō)明出現(xiàn)過(guò)1次掺炭。
引申一下，就可以解決字符串允許重復(fù)k次的子串長(zhǎng)度凭戴。

public int lengthOfLongestSubstring(String s) {
        int[] freq = new int[256];  //記錄字符出現(xiàn)的次數(shù)

        int l = 0, r = -1;  //滑動(dòng)窗口為s[l...r]
        int res = 0;

        while( l < s.length() ){
            if( r + 1 < s.length() && freq[s.charAt(r+1)] == 0)
                freq[s.charAt(++r)] ++;
            else
                freq[s.charAt(l++)] --;

            res = Math.max(res, r-l+1);
        }
        return res;
    }

Leetcode 438題：找到字符串中的anagram

List<Integer> res = new ArrayList();
        if(s.length() < p.length())
            return res;
        assert p.length() > 0;
        
        char[] arrS = s.toCharArray();
        char[] arrP = p.toCharArray();

        // 定義一個(gè) needs 數(shù)組來(lái)看 arrP 中包含元素的個(gè)數(shù)
        int[] freq_p = new int[26];
        // 定義一個(gè) window 數(shù)組來(lái)看滑動(dòng)窗口中是否有 arrP 中的元素涧狮，并記錄出現(xiàn)的個(gè)數(shù)
        int[] freq_s = new int[26];

        // 先將 arrP 中的元素保存到 needs 數(shù)組中
        for (int i = 0; i < arrP.length; i++) {
            freq_p[arrP[i] - 'a'] ++;
        }
        // 在s[l...r]中的元素與p進(jìn)行比對(duì)，一開(kāi)始這個(gè)區(qū)間里沒(méi)有元素么夫，所以r為-1
        int l = 0;
        int r = -1;
        //Sliding window: s[l...r] r - l + 1<= p.length()
        //if freq_s[r] < freq_p[r] r++
        //if freq_s[r] > freq_p[r]  freq_s[l]-- && l++者冤，也就是整個(gè)窗口左移
        //if freq_s[r] == freq_[r]
            //if r - l + 1 == p.length()
                //res.add(l) && l++ && freq_s[l]--
        // 右窗口開(kāi)始不斷向右移動(dòng)
        while ( r + 1 < arrS.length ) {
            
            if( r - l + 1 < arrP.length )
                freq_s[arrS[++r] - 'a'] ++;

            while( freq_s[arrS[r] - 'a'] > freq_p[arrS[r] - 'a'] && l  < arrS.length)
                freq_s[arrS[l++] - 'a'] --;

            if( r - l + 1 >= arrP.length ){
                res.add(l);
                freq_s[arrS[l++] - 'a'] --;
            }
        }
        return res;

Leetcode 76：最小覆蓋子串

 public String minWindow(String s, String t) {
       if (s.length() < t.length())
            return "";
        assert t.length() > 0;

        char[] arrS = s.toCharArray();
        char[] arrT = t.toCharArray();


        int[] freq = new int[128];
        int[] window = new int[128];
        int count = 0;

        for (char c : arrT) {
            freq[c]++;
        }


        int minLen = s.length() + 1;
        int startIndex = -1;

        // 在s[l...r)中的元素與p進(jìn)行比對(duì)，一開(kāi)始這個(gè)區(qū)間里沒(méi)有元素档痪，所以r為0
        int l = 0, r = 0;
        while (r < arrS.length) {

            if(freq[arrS[r]] == 0){
                r++;
                continue;
            }

            if ( window[arrS[r]] < freq[arrS[r]])
                count++;

            window[arrS[r++]]++;

            while (count == arrT.length) {
                if(r - l < minLen){
                    minLen = r - l;
                    startIndex = l;
                }
                if ( window[arrS[l]] == 0){
                    l++;
                    continue;
                }
                //給startIndex賦值
                //移動(dòng)左邊界,判斷count是否--
                //當(dāng)count不滿足條件涉枫，繼續(xù)移動(dòng)右邊界
                if(window[arrS[l]] == freq[arrS[l]]){
                    count--;
                }
                window[arrS[l++]]--;
            }
        }
        if (minLen == s.length() + 1)
            return "";

        return s.substring(startIndex, startIndex + minLen);
    }