最终挑战与 O(N) 的秘密（双指针）

介绍

我们已经走到了算法复杂度之旅的终点！我们已经看到了 Merge Sort O(N log N) 的强大以及 二分查找 O(log N) 的高速。
在这篇最后的文章中，我们将：

• 在一个高级挑战（“平方数问题”）中应用 O(N) 的知识；
• 揭示 Elixir Map 的 O(1) 承诺背后的技术秘密。

重新审视问题

给定一个已经排序好的列表 nums，返回该列表中每个数的平方组成的列表，同样保持有序。

朴素解法

把每个元素平方 → O(N)
对结果排序 → O(N log N)

总计：O(N log N)。

使用双指针的 O(N) 解法

技巧在于利用输入已经排序好的信息。由于负数的绝对值大时对应的平方也大，最大的平方总会出现在输入列表的两端。

双指针 技术从后向前（从最大到最小）构建结果：

1. 指针 l 指向开头（值 -4）；
2. 指针 r 指向末尾（值 10）；
3. 比较两端的平方；把较大的平方放入结果列表；
4. 相应的指针向内移动。

复杂度：O(N)。

Elixir 实现

在 Elixir 中，我们使用 Enum.reduce 来模拟指针的移动，并用 [square | acc]（前置）在 O(1) 的每一步中从后向前构建结果。

defmodule SortedSquares do
  @doc "使用双指针的 O(N) 解法，逆序构建结果。"
  def sorted_squares(nums) do
    # l: 左指针 (0), r: 右指针 (N-1)
    {result_reversed, _} =
      0..(length(nums) - 1)
      |> Enum.reduce({[], {0, length(nums) - 1}}, fn _, {acc, {l, r}} ->
        left_square = Enum.at(nums, l) * Enum.at(nums, l)
        right_square = Enum.at(nums, r) * Enum.at(nums, r)

        if left_square > right_square do
          # 左侧的更大，移动指针 l
          {[left_square | acc], {l + 1, r}}
        else
          # 右侧的更大（或相等），移动指针 r
          {[right_square | acc], {l, r - 1}}
        end
      end)

    result_reversed
  end
end

双指针技术小结

该技术保证我们每个元素只访问一次（O(N)），从而避免了最终排序的开销（O(N log N)）。

Elixir 中 Map 与 MapSet 的 O(1)

在本系列中，我们承诺 Elixir 的 Map 和 MapSet 的查找/插入是 O(1)。为什么如此快速？更重要的是，Elixir 如何在保证不可变性的前提下实现这一点？

答案在于 Erlang/Elixir 使用的底层数据结构：Hash Array Mapped Tries（HAMT）。

• Hashing：插入键（例如 :user）时，会先将其转换为 hash code（一个整数）。
• Trie（数字树）：该 hash code 充当在高分支度树中导航的路径。HAMT 只需下降少数几层即可定位到具体的值。
• Array Mapped：在每一层，使用一个小数组（“映射”）而不是大量指针，从而快速找到下一个分支。

不可变性的优势

当你在 Elixir 中更新一个 MapSet 时，系统 不会复制 整个结构。它会复用那些未被修改的旧树枝，仅为被修改的路径创建新节点。这种机制称为 结构共享（Structural Sharing）。

得益于 HAMT，O(1)（常数时间）的查找和插入承诺得以实现，且 Elixir 代码在 BEAM 上保持高速且安全的并发特性。

最后总结

现在，你已经对复杂度类别有了扎实的理解，能够识别 O(N²) 的瓶颈，并掌握了 Elixir 的工具（Merge Sort、MapSet 与 reduce）来编写不仅能工作而且能够高效扩展的代码。