第一步对撞双指针
最终作品第一步:补全 two_sum(有序数组,两数之和)。把两个下标用 / 连起来输出(目标 40)。 (本题用 g++ -std=c++17 -O0 编译。)
第二步快慢指针
补全 mid_index(找中点)和 has_cycle(判环,-1 表示到头)。输出:中点下标 / 无环判断 / 有环判断。 (本题用 g++ -std=c++17 -O0 编译。)
第三步两种窗口
补全 max_window(固定窗口最大和,k=3)和 min_len(和不小于 50 的最短长度)。两个结果用 / 连起来输出。 (本题用 g++ -std=c++17 -O0 编译。)
第四步差分
补全 range_add 和 restore,做 [0,2] 加 5、[1,3] 加 2,把前 5 个位置的值用 / 连起来输出。 (本题用 g++ -std=c++17 -O0 编译。)
交付四种技巧一起验收
这是这条路线的最终作品。对撞、快慢指针、固定窗口、暴力对照和差分都已给好,补全三处关键函数:has_cycle、min_len、restore。然后一次验完五条:对撞找和为 40 的两个下标是 2 和 3;中点是 2、无环判 false、有
百万数据的双重循环
n = 10^6 时,O(n²) 的双重循环大约要做【0】次运算。
补写最短达标窗口
场景:实验机上 ~/work/tp/minwin.cpp 读入 n、target 和 n 个正整数,要输出和不小于 target 的最短连续子段长度(没有就输出 0)。min_len 还没写。 任务:补全 min_len(右扩左收的可变窗口
三十万个数的两数之和
场景:~/work/tp/pairs.cpp 读入一个严格递增的数组和 target,统计有多少对下标 i<j 满足 a[i]+a[j]=target。结果是对的,可它是双重循环,n = 30 万时要跑很久。 任务:改写成对撞双指针,
修好倒序输出的下溢
场景:~/work/tp/back.cpp 读入 n 个数(n 可能是 0),倒着输出。它用 size_t 下标从 v.size() - 1 往下走,一运行就越界崩溃。Makefile 带了内存检查。 任务:修好倒序循环,n = 0 时输出
修好收缩时的计数
场景:~/work/tp/kdist.cpp 求字符串里「最多含 K 种字符」的最长连续子串长度。左端收缩时只把计数减一,减到 0 的字符没有从 map 里删掉,结果时对时错。 任务:修好收缩那一段。make 编译后用 sample.txt