课程大纲 第 55 课,共 148 课 · 不用缓存的速度
不用缓存的速度

双指针,不用表

为什么重要 “找出两样加起来等于 X 的东西”有一个有名的答案:把所有东西放进一个集合,然后查找它的搭档。它很快,但它需要所有数据的一份副本。当数据有序时,你几乎完全不需要内存。

一个礼品服务以一个固定的组合价出售由两件不同商品组成的组合。商品价目表是有序的、没有重复,存放在一个空闲内存非常少的嵌入式设备上。对于一个组合价,你需要知道有多少对商品的价格加起来恰好等于那个价格。

prices = [1, 2, 3, 4, 5, 6]   # sorted, no repeats
count_pairs(Tape(prices), 7)    # 3: (1, 6), (2, 5), (3, 4)
轮到你了

编写 count_pairs(tape, target)。tape 是一个由整数价格组成的 Tape,升序排列,没有重复。返回有多少对由两件不同的商品组成、加起来恰好等于 target 的组合(每一对只算一次)。预算:对于 20,000 件商品,最多读取 60,000 个值,并且在你的函数运行时最多使用 16,000 字节的工作内存(用 tracemalloc 测量;一个包含 20,000 个价格的集合或列表超过 150,000 字节)。len(tape) 是免费的。

发现这节课有问题?报告它 · 就这节课提问

这个练习即将开放

完成它前面的那一课,这一课就会解锁。整门课程免费,无需账号,而且你现在就可以阅读这节课。