第一连：滑动窗口

正数数组arr，求累加和等于sum的子数组最长是多长？

ps：子数组、子串一定是连续的
因为是正数数组，所以数组范围与累加和sum有严格的单调性，一旦发现有单调性，那么一定有优雅的解法
- 1. 两个指针往中间移动
- 1. 一个窗口不停滑动

这里用窗口

解释下为什么

比如这里L 到 R 的窗口累加和正好等于sum时，意味着以0开头的所有子数组中只有这一个是达标的，因为R再往右扩必超sum。

那么任意一个X开头扩到R时累加和正好等于sum，说明以x开头的所有子数组中只有这一个时达标的。
但如果一直往右扩，直到＞sum时都没遇到过== sum 的，说明以x开头的所有子数组中没有答案。此时让L往左动意味着放弃x开头的答案了，去求x +1 开头的

所以我们在这个过程中其实找到了所有的答案。

当累加和等于sum的时候，你让谁先动都无所谓，因为你让R动， L..R 必大于sum，那么L就得动了，若你让L先动， L..R 必小于sum，那么R就得动了

如果R往右扩到越界了，说明这个开头及它后面所有的开头都不可能有答案，直接break

public static int getMaxLength(int[] arr, int k) {
    if (arr == null || arr.length == 0 || k < 0) {
        return 0;
    }
    int L = 0;
    int R = 0;
    int sum = arr[0];
    int len = 0;
    while (R < arr.length) {
        if (sum < k) {
            R++;
            if (R == arr.length) {
                break;
            }
            sum += arr[R];
        } else if (sum > k) {
            sum -= arr[L++];
        } else {
            len = Math.max(len, R - L + 1);
            sum -= arr[L++];
        }
    }
    return len;
}

第二连：

数组中正数、负数、0都有，问子数组中累加和等于 K中最大长度是多少？

数组范围跟累加和单调性没有了，范围增大，累加和有可能变大、变小
这时候范围跟累加和的单调性就没有了，范围增大，累加和有可能增大，
- 这时候有两种常见解法
  - 1）以每个位置为开头求一个结果，求出所有开头的结果，答案必在其中
  - 2）以每个位置为结尾求一个结果，求出所有结尾的结果，答案必在其中

这里用结尾解法

数组0~17位置，K = 200, 假设现在告诉你结论：0~17位置累加和是1000，又告诉你0~5是数组中最早出现累加和为800的范围，那么你就一定知道6~17是累加和等于k（200）的最长长度

流程还没讲完，但是先来过一下例子理解一下
有一个map

key存放累加和，value放这个累加和最早出现的位置

（sum - K）这个和最早出现的位置，去map里找，若找不到，说明以5结尾的时候根本没答案，然后map里put（5，0）
找累加和为1最早出现的位置，去map里找，没答案，然后map里put（11， 1）

找累加和为5最早出现的位置，——> 0位置，那么下一个位置到当前位置就是累加和为K==10的答案
找累加和为2最早出现的位置，没答案，更新map （12， 3），继续
找累加和为2最早出现的位置，没答案， 注意！此时map里已经有（12， 3）了，不用更新map，因为map里存的是累加和最早出现的位置

找累加和为2最早出现的位置， —-> 5, 那么1~5范围就是答案长度

这个流程有没有毛病？有！
整个流程开始前，空map里必须躺一条记录，就是（0， -1），累加和为0的最早位置出现在-1，要是没有这条记录的话，比如0~i 的累加和 - k正好等于0，那么去map找是找不到的，若map里有这条记录，那么答案长度范围就是-1的下一个位置，也就是0~i
举个例子理解一下

如果你不添（0， -1）这条记录，那么在这个例子中，你就会错过最长答案，也就是找2~2，但如果你有添（0， -1）, 那么map里的（0， 1）记录就不会被加进去，你找到的答案就是0~2

public static int getMaxLength(int[] arr, int k) {
   if (arr == null || arr.length == 0) {
       return 0;
   }
   HashMap<Integer, Integer> map = new HashMap<>();
   map.put(0, -1);
   int len = 0;
   int sum = 0;
   for (int i = 0; i < arr.length; i++) {
       sum += arr[i];
       if (map.containsKey(sum - k)) {
           len = Math.max(len, i - map.get(sum - k));
       }
       if (!map.containsKey(sum)) {
           map.put(sum, i);
       }
   }
   return len;
}

打开魔盒

有了第二连的基础之后，现在看这道题一个数组，有正有负有0，问含有1的数量和含有2的数量一样多的子数组中，子数组的最长长度是多少？

解法，遍历，遇到不是1和2的，都让它变成0，遇到1，维持不变，遇到2，让它变-1，那么问题就变成求累加和为0的子数组中最大长度

第三连

一个数组，有正有负有0，所有子数组中累加和≤K的，达标，问达标子数组中最大长度是多少？

先给概念

以 i 开头的数组中，累加和最小的范围长度是多少？
预处理结构： 2个辅助数组，
- minSum[ ]
  - 记录子数组以 i 位置开头往右到哪里（j）是以i为开头的所有子数组中可能性中累加和最小的
- minSumEnd[ ] 和上边那个数组搭配使用的
  - 记录上边那个右边界 j
- 从右往左填
- 其实接下来是个动态规划，看右一个位置有没有利可图，
- 从右往左遍历一遍，这俩数组就很顺利的生成好了
这两个数组求好了，我们就知道i往后所有可能性中的最小累加和及其右边界，

假设现在以0开头 minSUm[0]是35， minSumEnd[i]是7，说明没答案，
假设现在以0开头 minSUm[0]是5， minSumEnd[i]是7呢？那么
往右一段一段扩嘛，直到扩到不行了，你就知道0开头时候的所求答案了。
所以你以为我是要以0为开头往右扩，，。。。以1为开头继续往右扩。。。。。以2为开头往右扩？ no ，这样就变成O(N^2)了
- 假设现在K=100，然后现在0~29的累加和是90，扩到30位置就扩不动了，
  - 那么1位置开头我不从头开始扩，我就用90 - arr【0】，然后再看30这段能不能扩进来，
    - 我不从头了，我把开头踢出去，然后看我之前不能扩动的块能不能包含进来
      - 这种做法叫做：舍弃可能性
      - 我就维持住一个窗口，不回退，我看它有没有往右的可能性，若没有，那以它开头的本来也不是我要的
      - 举个例子
      - 如果不优化，接下来是这么做的
      - 如果我们每次都以每个位置开头的从头扩，那我们可以得到所有结果，不错过
      - 但如果优化，是这样做的
        
        把0踢出去，看能不能往右扩，虽然以1开头的答案是1~2，但是我们之前已经求了以0开头的答案0~4，我没必要再去求比我弱的可能性，当个屁放了，我只求能更长的可能性
- 注意，如果你把开头踢出去的方式是累加和直接减开头，那么
- 你有可能把你窗口弄没了
- 窗口已经没有数了，你依然扩不动，咋办？
- 让end跳到i + 1

所以总的来说，它的时间复杂度是O(N), 求两个活宝是O（N），然后流程只会前进不会后退，所以也是O（N）
这道题的精髓就是舍弃了部分可能性，但不会影响到我的答案，但这又是优化的基础 ```java public static int maxLengthAwesome(int[] arr, int k) { if (arr == null || arr.length == 0) {
```
   return 0;
```
} int[] minSums = new int[arr.length]; int[] minSumEnds = new int[arr.length]; minSums[arr.length - 1] = arr[arr.length - 1]; minSumEnds[arr.length - 1] = arr.length - 1; for (int i = arr.length - 2; i >= 0; i—) {
```
   if (minSums[i + 1] < 0) {
       minSums[i] = arr[i] + minSums[i + 1];
       minSumEnds[i] = minSumEnds[i + 1];
   } else {
       minSums[i] = arr[i];
       minSumEnds[i] = i;
   }
```
} int end = 0; int sum = 0; int len = 0; // i是窗口的最左的位置，end扩出来的最右有效块儿的最后一个位置的，再下一个位置 // end也是下一块儿的开始位置 // 窗口：[i~end) for (int i = 0; i < arr.length; i++) {
```
   while (end < arr.length && sum + minSums[end] <= k) {
       sum += minSums[end];
       end = minSumEnds[end] + 1;
   }
   len = Math.max(len, end - i);
   if (end > i) {  // 窗口内还有数 [i~end) [4,4) 
       sum -= arr[i];
   } else {  // 窗口内已经没有数了，说明从i开头的所有子数组累加和都不可能<=k
       end = i + 1;
   }
```
} return len; }

```

算法进阶

数组累加和问题三连

第一连：滑动窗口

第二连：

打开魔盒

第三连