# 双指针，窗口类

### [Minimum Size Subarray Sum](https://leetcode.com/problems/minimum-size-subarray-sum/)

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

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

```java
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](https://leetcode.com/problems/maximum-size-subarray-sum-equals-k/)

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

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

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

```java
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](https://leetcode.com/problemset/algorithms/)

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

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

```java
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](https://leetcode.com/problems/minimum-window-substring/)

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

```java
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 的条件。**

```java
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)] ++;
        }
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mnunknown.gitbook.io/algorithm-notes/two_pointers/614-_two_pointers-_shuang_zhi_zhen_ff0c_chuang_kou.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.