双指针，窗口类

Minimum Size Subarray Sum

这种看起来有点 greedy 味道的双指针都不同程度上利用后面状态的增长性质，直接排除一些元素，减少搜索范围。

在这道题里，如果 [i - j] 的 subarray 已经 >= target 了，考虑任何 j 以后的元素都是没有意义的，因为数组都是正数，依然会 >= target，长度还一定比当前的长。

public class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        if(s < 0 || nums == null || nums.length == 0) return 0;
        int size = Integer.MAX_VALUE;
        int sum = 0;
        int j = 0;

        for(int i = 0; i < nums.length; i++){
            while(j < nums.length && sum < s){
                sum += nums[j++];
            }
            if(sum >= s) size = Math.min(j - i, size);
            sum -= nums[i];
        }

        if(size == Integer.MAX_VALUE) return 0;

        return size;
    }
}

Maximum Size Subarray Sum Equals k

这题的做法其实和上一题没啥关系，也不属于这个分类。。不过看在长得非常像的份上就一起写了吧 = =

这题其实是 prefix sum array + two sum，利用前缀和数组实现快速区间和查询，同时 two sum 的方法快速地位 index.

这种 prefix sum 的下标要格外小心，很容易标错。。target value 差也是，写之前多手动过几个 case 保平安。

public class Solution {
    public int maxSubArrayLen(int[] nums, int k) {
        if(nums == null || nums.length == 0) return 0;
        // Key: prefix sum   
        // Value: index
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        map.put(0, 0);
        int sum = 0;
        int size = 0;

        for(int i = 0; i < nums.length; i++){
            sum += nums[i];
            if(map.containsKey(sum - k)){
                size = Math.max(size, i - map.get(sum - k) + 1);
            }
            if(!map.containsKey(sum)) map.put(sum, i + 1);
        }

        return size;
    }
}

Longest Substring Without Repeating Characters

这题其实我几周前做过了，放在这个分类里，用分类模板再重构一次吧。

代码上确实简洁了很多，而且一次 AC.

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.length() <= 1) return s.length();
        int max = 1;
        boolean[] hash = new boolean[256];
        int j = 0;
        for(int i = 0; i < s.length(); i++){
            while(j < s.length()){
                if(!hash[s.charAt(j)]){
                    hash[s.charAt(j++)] = true;
                } else {
                    break;
                }
            }
            max = Math.max(max, j - i);
            hash[s.charAt(i)] = false;
        }

        return max;
    }
}

Minimum Window Substring

• 我的第一种写法 validWindow 函数扫整个 target string，时间爆炸，1200ms + ，改成只扫 256 个 ASCII 字符立刻就变成 35ms 了。

public class Solution {
    public String minWindow(String s, String t) {
        if(t.length() > s.length()) return "";

        int[] window = new int[256];
        int[] count = new int[256];

        for(int i = 0; i < t.length(); i++){
            count[t.charAt(i)] ++;
        }

        int j = 0;
        int size = Integer.MAX_VALUE;
        String rst = "";
        for(int i = 0; i < s.length(); i++){
            while(j < s.length() && !validWindow(t, window, count)){
                window[s.charAt(j++)] ++;
            }
            if(j - i < size && validWindow(t, window, count)){
                rst = s.substring(i, j);
                size = j - i;
            }
            window[s.charAt(i)]--;
        }

        return rst;
    }

    private boolean validWindow(String t, int[] hash, int[] count){
        for(int i = 0; i < 256; i++){
            if(hash[i] < count[i]) return false;
        }

        return true;
    }
}

更好的写法是我改写九章的答案，9ms，重点在于 validWindow() 函数的优化。

• 对 Target string 做预处理，返回 int[] hash 和需要 match 的字符串数量；

• j 作为靠前指针，每次都在 hash 里把对应字符 -1； 如果对应的 count 原本为正数，match 字符数量 curCount++; 否则对应的位置就会变成负数 count，不会被记入 curCount 的增减中。

• 于是 int[] hash 里面的正负，代表了还需要 match 的个数，控制了 curCount 的增减； curCount 就可以作为判断窗口是否 valid 的条件。

public class Solution {
    public String minWindow(String s, String t) {
        if(t == null || t.length() == 0 || t.length() > s.length()) 
            return "";
        int targetCount = t.length();
        int curCount = 0;
        int[] hash = new int[256];
        preprocess(hash, t);
        int j = 0;
        String rst = "";
        int minSize = Integer.MAX_VALUE;

        for(int i = 0; i < s.length(); i++){
            while(j < s.length() && curCount < targetCount){
                hash[s.charAt(j)] --;
                if(hash[s.charAt(j)] >= 0) curCount ++;
                j ++;
            }
            if(curCount >= targetCount && j - i < minSize){
                minSize = j - i;
                rst = s.substring(i, j);
            }
            hash[s.charAt(i)] ++;
            if(hash[s.charAt(i)] > 0) curCount --;
        }

        return rst;
    }

    private void preprocess(int[] hash, String t){
        for(int i = 0; i < t.length(); i++){
            hash[t.charAt(i)] ++;
        }
    }
}