不用缓存的速度
双指针,不用表
你以前学过这门课程吗?
这样我们只统计你一次。只会发送你的答案,以及你的匿名进度。
为什么重要 “找出两样加起来等于 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) 是免费的。
本课已完成。干得好。
这个练习即将开放
完成它前面的那一课,这一课就会解锁。整门课程免费,无需账号,而且你现在就可以阅读这节课。
这个浏览器屏蔽了 learn.floati.life 的 Cookie,所以你在这里完成的课程无法按顺序打开。请允许这个网站使用 Cookie,然后重新加载。