【优选算法 — 滑动窗口】长度最小的子数组 & 无重复字符的最长子串
长度最小的子数组
题目解析：
对于示例一
对于剩下两种示例：
解法一：暴力枚举
把所有的子数组全部枚举出来，并且枚举出的每一个子数组求和判断，返回长度最小的子数组；
时间复杂度 ：
枚举子数组 N^2 ，求和 N —> O(N^3)
数组中全都是正整数，所以加的数越多，和就越大，所以这就可以利用单调性来优化
优化暴力枚举，要让时间复杂度从 O(N^3) 优化到 O(N^2)
我们先定义出左区间 left ，然后不着急枚举右区间 right，先定义一个变量 sum ，来统计以 left 为左区间的所有子数组的和：
刚刚的暴力枚举，是先枚举右边，并且每枚举一次，都要判断当前子数组是否是合适的子数组 ；
而优化的方法为，定义一个sum，在 right 向右枚举时，每枚举一个数，都把这个数加到 sum 上
优化后，就可以省去找到子数组后（找到合适的位置，固定 left 和 right ），从前往后遍历，再相加的步骤；
此时我们就找到了一个合适的子数组，长度为4，既然已经找到合适的子数组，并且数组中都是正整数，那么我们就没有必要再让 right 继续往后枚举了，因为要返回的是长度最小的子数组；
此时就需要让 left++，此时，我们不需要着急更新 right，先计算 新left 和当前 right 组成的子数组 sum 是否满足条件；
所以在找到合适的子数组后，处理好后，先要让 sum = sum - nums[left] ，再让 left++即可
解法二：利用单调性，使用 “同向双指针”（“滑动窗口”）
（如果遇到在 right++ 后 依旧是 sum > target ，让 left++，而不是 right--）
如果 sum < target，right++ (进窗口)；sum > target，left++（出窗口）
因为在找合适子数组的过程中，left 和 right 一直是向右移动的，right 在 left++ 之后，是不会回退的，所以叫“同向双指针” ，“同向双指针”，又叫“滑动窗口”；
当我们发现可以利用单调性，使得两个指针都可以不会退（本题因为给的数组元素都是正整数，可以利用单调性，进而运用“滑动窗口”思想）
- 先初始化左窗口和右窗口（用 left 和 right 标记左区间和右区间，区间代表窗口）
- 进窗口 (right++)
- 判断（这个题需要在判断结果的时候更新结果，其他题目可能在进窗口更新结果）
- 出窗口 (right++)
- 循环进窗口和出窗口的过程 (回退到判断的步骤)
(更新结果的步骤是就题论题的，有的题目是进窗口时更新结果，有的是判断的时候才更新结果）
滑动窗口能保证正确性，因为通过利用单调性，规避了很多没有意义的枚举行为，一定能在不断更新的过程中，得到一个最终的结果，这个结果就一定是正确的。
时间复杂度
哪怕代码是两层 for 循环，但是根据实际情况，我们每一步操作都只会让 left 或者 right 向后移动一格，最坏的情况：
刚开始初始化好指针后，就在判断下执行进窗口的操作（right++），在right = length 后，程序又通过判断执行出窗口操作（left++），这种最坏的情况操作 left 和 right 的次数为 2N；
所以时间复杂度为 O(N)
编写代码
错误代码：
正确代码 ：
无重复字符的最长子串
解法一：暴力枚举 + 哈希表（判断字符是否重复出现）
- 暴力枚举，就是以某一个字符为起点，开始向后遍历字符串；
- 并且把遍历到的每一个字符，都放入 hash 表 中，进行判断当前遍历字符是否重复出现；
- 如果重复出现，则停止遍历，统计当前子串长度（哈希表中的元素个数），并且让起点向后挪动一位；
时间复杂度：
分析最坏情况下的时间复杂度，最坏情况下，因为是暴力枚举，从起点开始向后遍历字符串，并且起点从 字符串的第一个元素 到 字符串的最后一个元素 ；这个过程枚举到的所有子串中，返回最大子串长度；
所以时间复杂度是 O(N^2)
我们定义 left 指针指向起点并且固定，right 指针从 left 指针开始遍历；
每次遍历到一个字符，就判断该字符是否出现在哈希表中；
直到来到出现重复字符的位置，并且 right 记录下该字符的位置 ；
如果是暴力枚举，在 right 指向重复字符位置，记录下当前子串长度；
记录下当前子串长度之后，left往后挪动一位，right 重新回到 left 指针的位置;
然后继续重复上述过程；
方法二：滑动窗口
当 right 到达重复字符的位置，然后统计当前子串的长度；
然后 left 向后挪，挪动到当前子串中，与 right 所指向的字符相同的字符，所在的位置的后一位；
此时，right 无需再像暴力枚举一样，又回到 left 之前的位置，因为在 left 按照上面的规则，移动好位置后，新的 left 与 right 之间，是没有重复元素的；
此时，继续向后挪动 right 即可；
上述情况，left 和 right 移动的方向相同，所以这种方法就是滑动窗口。
对于上面这种题，对于我们最重要的启发，就是能分析出为什么使用滑动窗口：
要想清楚这题的做法是滑动窗口，要能根据例子，推断出 left 和 right 两个指针不用回退，并且 left 和 right 的移动情况（不一定是只后挪一位）
编写代码
对于本题，我们并不需要真的去 new 一个哈希表，可以用数组模拟哈希表；
只需要 new 一个最大容量为 128 的数组即可，因为所有我们常见的字符数为128；
数组的下标表示，每个字符的 ASCLL 码值；
如果该字符出现一次，该字符的 ASCLL码值对应的数组下标元素 +1；
时空复杂度
时间复杂度：
O(N)，虽然有两层循环，但是与上一题类似，要根据具体的情况分析时间复杂度；
空间复杂度：
原文地址：https://blog.csdn.net/2402_84916296/article/details/143574972
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！