C++实现漂亮数组问题的高效解法

漂亮数组问题是算法领域中一道经典的分治策略应用题目，其核心定义为：对于一个长度为 n 的数组 A，若对任意满足 i < k < j 的三元组 (i, k, j)，都不存在等式 A[i] + A[j] = 2 \times A[k]，则称数组 A 为漂亮数组。本文将基于分治思想，提供两种C++实现方案，兼顾效率与可读性。
一、问题核心分析
观察漂亮数组的定义，等式 A[i] + A[j] = 2 \times A[k] 本质是要求数组中不存在等差子序列。
从奇偶性角度可推导关键性质：
1. 奇数 + 偶数 = 奇数，无法被 2 整除，因此奇数数组和偶数数组拼接后，不会产生跨区间的等差三元组。
2. 若数组 A 是漂亮数组，则 2 \times A - 1（全奇变换）和 2 \times A（全偶变换）得到的数组也为漂亮数组。
基于此，分治策略的思路为：递归将数组拆分为左奇右偶两部分，分别构造漂亮数组后拼接，最终得到结果。
核心逻辑说明
- 递归版：通过递归将问题分解为更小的子问题，分别构造左右子数组后，进行奇偶变换再拼接。
- 迭代版：从长度为1的数组开始，循环进行奇偶扩展，直到数组长度达到 n，避免了递归的栈开销。

复杂度分析
- 时间复杂度：O(n \log n)，每次递归/迭代都会遍历当前数组，总共需要 \log n 层。
- 空间复杂度：递归版 O(n \log n)（栈空间+结果空间），迭代版 O(n)（仅结果空间）。

总结
本文提供的两种方案均基于分治策略，从奇偶性角度切入，完美解决漂亮数组的构造问题。递归版适合理解算法思想，迭代版更适合实际工程应用。该思路不仅适用于漂亮数组问题，还可迁移到其他涉及等差序列排除的算法场景中。