让窗口滑起来
补全 max_window:建好初始窗口之后,每滑一格加上新进来的、减去出去的,一路记住最大的和。
把每个窗口的和都列出来
补全代码:算出每一个长度为 3 的窗口的和,按顺序拼起来输出(用 / 隔开)。
⚠️ 一进一出到底省了多少
数组长 n、窗口长 k:每次重算是 (n-k+1) * k 次加法,一进一出是 k + (n-k) * 2 次。 补全两个函数,算 n=1000、k=100 的情况,拼起来输出(重算在前)。
可变窗口和固定窗口的区别
可变窗口和固定窗口的区别是【0】。
什么时候该收缩左端
可变窗口里,收缩左端的时机是【0】。
为什么两端都只往右走还是 O(n)
可变窗口的两个指针都只往右,总代价是 O(n),因为【0】。
和不小于 50 的最短窗口有多长
数组是 [17, 8, 15, 13, 23, 24, 19]。运行下面这段程序: def min_len(a, target): lo = 0 s = 0 best = len(a) + 1 for hi
最长的不重复子串有多长
字符串是 abcabcbb。运行下面这段程序: def longest_unique(s): seen = {} lo = 0 best = 0 for hi in range(len(s)):
求和不小于目标的最短窗口
补全 min_len:右端一路扩大,一旦满足就把左端往里收,记住最短的长度。
求最长的不重复子串
补全 longest_unique:右端每进一个字符,如果它在窗口里出现过,就把左端跳到那次出现的后面。