如何利用 Set 配合迭代器实现对无限序列（如斐波那契）的局部截取-js教程-PHP中文网

核心思路是用迭代器按需生成无限序列值，用Set以O(1)平均复杂度快速判断是否满足条件并及时终止，聚焦“前N个符合条件的值”而非索引区间截取。

用 set 配合迭代器对无限序列（比如斐波那契）做局部截取，核心思路是：**用迭代器按需生成值，用 set 快速判断是否命中目标条件，一旦满足就终止，避免全量计算**。它不追求“取出某一段索引区间”，而是聚焦“满足某业务规则的前 n 个值”——比如“前 10 个偶数斐波那契数”或“所有 ≤ 1000 的斐波那契数”。

为什么用 Set 而不是 list 或其他结构？

Set 的 has()（JavaScript）或 in（Python）平均时间复杂度是 O(1)，适合高频查找。当你需要反复判断某个数是否属于预设集合（比如质数集、平方数集、自定义黑名单/白名单），Set 比遍历数组快得多。

例如：找出斐波那契数列中前 5 个也是质数的数 → 先把质数打表成 Set，再用迭代器逐个生成斐波那契数，查 Set 判断是否为质数
又如：跳过某些“禁止值”（如 8、13、21），只保留其余斐波那契数 → 把禁止值存进 Set，生成时过滤

基础组合：迭代器 + Set 过滤逻辑

以 JavaScript 为例，用 generator 实现斐波那契迭代器，配合 Set 做条件拦截：

function* fibonacci() {
  let a = 0, b = 1;
  while (true) {
    yield a;
    [a, b] = [b, a + b];
  }
}
<p>// 定义要过滤掉的值（比如不想看到 8、13、21）
const forbidden = new Set([8, 13, 21]);</p><p>// 局部截取：取前 10 个不在 forbidden 中的斐波那契数
function takeFiltered(iter, filterSet, limit) {
const result = [];
for (const val of iter) {
if (!filterSet.has(val)) {
result.push(val);
if (result.length >= limit) break;
}
}
return result;
}</p><p>console.log(takeFiltered(fibonacci(), forbidden, 10));
// → [0, 1, 1, 2, 3, 5, 34, 55, 89, 144]（跳过了 8/13/21）
</p>

更实用的场景：按数值范围截断

无限序列不能无限跑，常需“≤ N”的自然边界。这时 Set 可配合范围检查一起用，比如只保留既是斐波那契数、又在某个数集（如前缀和集合）里的值：

C++ 示例中提到用 set::count() 配合前缀和判断是否存在 → 本质是把“合法值域”预先建好 Set，再让斐波那契迭代器喂值进去匹配
Python 中可写：valid_targets = set(compute_prefix_sums(1000))，然后 for f in fib_iter(): if f in valid_targets: collect.append(f)
关键点：Set 构建是一次性开销，后续每次 in 查找都是常数时间，整体仍保持 O(k)，k 是实际生成并检查的项数

注意事项与常见坑

这种组合看似简单，但容易忽略边界和语义一致性：

斐波那契起始定义要统一：0,1 开头还是 1,1 开头？Set 中的值必须与迭代器产出值严格对齐
Set 不支持范围查询（比如“找大于 100 的第一个值”），它只回答“有没有”。想实现范围截断，还得靠迭代器内部加 if (val > 100) break 这类显式控制
内存上，Set 存的是键值，不是引用；迭代器本身不保存历史，所以组合后仍保持低内存占用——真正做到了“按需 + 查找快”