中间相遇
Meet-in-the-middle - 一种优化方式解决方案，包括将原始问题分成两半，分别独立解决，然后通过合并两半的解决方案来获得原始问题的解决方案。
因此，如果满足两个条件，则使用
meet-in-the-middle 是有意义的。
1) 解决一半问题所需的时间渐近小于解决整个问题的时间。
2) 通过解决半个问题，可以得到原整个问题的解，同时比只解决整个问题渐进地更快。
例子
假设有四个整数数组
A、
B、
C 和
D。有必要从每个数组中恰好选择一个数字，使这些数字的总和等于零。您可以使用一种简单的解决方案，即简单地枚举所有可能的选项。这适用于
O(n4)。
然而，我们可以使用
meet-in-the-middle。
请注意，
a + b + c + d = 0 等同于
(a + b) = -(c + d)。
让我们把任务分成两半，即前半部分我们将只使用数组
A和
B，后半部分只使用
C 和
D。
让我们在前半部分遍历所有可能的
(a + b)选项，并将所有值存储在哈希表中（
unordered_map，
HashMap 之类的。）。这在 O(n2) 中有效。
现在我们将在下半部分迭代所有可能的选项 (c + d)。在考虑某个选项时，我们会检查哈希表中是否有与当前符号相反的和相关联的值（然后我们找到两个倒数加起来为零）。这部分也适用于 O(n2)。
我们这里没有单独的“answer merge”阶段；一方面，我们在解决每一半的过程中这样做了。大多数任务都会有类似的情况。
我们最终在 O(n2) 中使用 meet-in-the-middle 解决了这个问题。
值得注意的是，meet-in-the-middle 在优化指数解时最常使用，这会显着影响运行时间。