Leetcode 209题： 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的连续子数组，返回 0。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-size-subarray-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这种连续子数组的问题，暴力解法，也就是列出所有的子数组来进行求和，再一一比对，符合要求的存储子数组的长度，最后输出最小的长度，这会导致O(n^3)的复杂度。

 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 ++){
                    //如果要查看子数组的序列，可打印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;
    }

使用滑动窗口，可以将复杂度下降至O(n)，其中两个指针l与r，分别指向窗口的左右边界，当窗口内数值的和大于s时，左边界往前移，去除最左边的数值，如果小于s时，则右边界往前，新增加一个数值。

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题： 无重复字符的最长字串

这里使用了一个小技巧：每一次一个新的字符再加入子串时，都需要判断一下这个字符是否已经出现过，可以使用一个新的数字，它的索引对应字符的ASCII码，这里也可以同时处理大小写不敏感的问题。
当这个索引对应的值为0时，就说明未出现过，为1时，就说明出现过1次。
引申一下，就可以解决字符串允许重复k次的子串长度。

public int lengthOfLongestSubstring(String s) {
        int[] freq = new int[256];  //记录字符出现的次数

        int l = 0, r = -1;  //滑动窗口为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();

        // 定义一个 needs 数组来看 arrP 中包含元素的个数
        int[] freq_p = new int[26];
        // 定义一个 window 数组来看滑动窗口中是否有 arrP 中的元素，并记录出现的个数
        int[] freq_s = new int[26];

        // 先将 arrP 中的元素保存到 needs 数组中
        for (int i = 0; i < arrP.length; i++) {
            freq_p[arrP[i] - 'a'] ++;
        }
        // 在s[l...r]中的元素与p进行比对，一开始这个区间里没有元素，所以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++，也就是整个窗口左移
        //if freq_s[r] == freq_[r]
            //if r - l + 1 == p.length()
                //res.add(l) && l++ && freq_s[l]--
        // 右窗口开始不断向右移动
        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进行比对，一开始这个区间里没有元素，所以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赋值
                //移动左边界,判断count是否--
                //当count不满足条件，继续移动右边界
                if(window[arrS[l]] == freq[arrS[l]]){
                    count--;
                }
                window[arrS[l++]]--;
            }
        }
        if (minLen == s.length() + 1)
            return "";

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