2501. 数组中的最长平方序列
💡
原文英文，约600词，阅读约需3分钟。
📝
内容提要
给定一个整数数组，寻找最长的平方序列，要求序列长度至少为2，且每个元素是前一个元素的平方。如果没有平方序列，返回-1。使用集合快速查找平方值，遍历数组构建序列并记录最长长度，时间复杂度为O(n log n)。
🎯
关键要点
- 给定一个整数数组，寻找最长的平方序列，要求序列长度至少为2。
- 平方序列的定义是：排序后每个元素（除了第一个元素）是前一个元素的平方。
- 如果没有平方序列，返回-1。
- 使用集合快速查找平方值，遍历数组构建序列并记录最长长度。
- 时间复杂度为O(n log n)，空间复杂度为O(n)。
- 示例1：输入[4,3,6,16,8,2]，输出3，平方序列为[4,16,2]。
- 示例2：输入[2,3,5,6,7]，输出-1，表示没有平方序列。
- 解决方案包括：使用集合进行快速查找，遍历数组构建平方序列，跟踪最大长度。
- 排序数组以确保检查序列时按升序进行，避免冗余检查。