求解元素≥2的互异整数集的最大完美子集大小

给定由互不相同、取值均≥2的整数组成的列表，完美子集需满足以下条件：

• 子集大小≥2
• 子集元素按升序排列后，对所有合法索引i均满足a[i] * a[i] = a[i+1]
  要求返回所有完美子集的最大大小。朴素解法通过逐个遍历列表元素，统计以每个元素为起点的完美子集长度后取最大值，存在大量重复计算，开销较高。

完美子集按升序排列后，本质是一个形如x, x², x⁴, x⁸, ...的序列，每个元素是前一个元素的平方。朴素解法效率低的核心原因是重复统计：对于一个长度为k的上述序列，朴素法会从序列的k个元素分别出发向后统计，产生k+(k-1)+...+1 = O(k²)次重复查询。
优化的核心是只从序列的最小起点出发统计长度，跳过所有序列中间的元素：

1. 先将所有元素存入哈希集合，把元素存在性的查询时间降到O(1)
2. 将列表按升序排序，从小到大遍历元素：如果当前元素的平方根是整数，且这个平方根存在于原列表中，说明当前元素一定属于某个更小元素作为起点的序列，已经被统计过，直接跳过即可
3. 仅对真正的序列起点，向后不断查询平方值是否存在，统计该起点对应的最长序列长度，更新全局最大值

• 初始化哈希集合存储所有列表元素，用于O(1)时间判断元素是否存在
• 将列表升序排序，初始化全局最大长度为1
• 遍历排序后的每个元素：
  • 计算当前元素的整数平方根，若平方根的平方等于当前元素、且平方根在哈希集合中，说明当前元素不是序列起点，直接跳过
  • 若为序列起点，初始化当前序列长度为1，循环判断当前值的平方是否在集合中：存在则序列长度+1，更新当前值为其平方，直到平方值不存在为止
  • 用当前序列长度更新全局最大长度
• 遍历结束后，若全局最大长度≥2则返回该值，否则说明不存在符合要求的完美子集，返回0

import math

def max_perfect_subset_length(nums):
    num_set = set(nums)
    sorted_nums = sorted(nums)
    max_len = 1
    for num in sorted_nums:
        # 计算整数平方根，避免浮点数精度误差
        sqrt_num = math.isqrt(num)
        # 非序列起点，跳过避免重复计算
        if sqrt_num * sqrt_num == num and sqrt_num in num_set:
            continue
        current = num
        current_len = 1
        while current * current in num_set:
            current_len += 1
            current *= current
        max_len = max(max_len, current_len)
    # 完美子集要求大小≥2，无符合条件子集返回0
    return max_len if max_len >= 2 else 0

• 时间复杂度：排序步骤耗时O(n log n)，遍历统计阶段每个元素最多被访问1次，总耗时O(n)，整体时间复杂度为O(n log n)，远优于朴素解法最坏情况下的O(n²)复杂度
• 空间复杂度：需要O(n)的哈希集合存储元素，空间复杂度为O(n)

输入[2,3,4,16,256,9]，最长完美子集为[2,4,16,256]，返回值为4
输入[2,3,5,7]，无符合要求的完美子集，返回值为0
输入[3,9,81,6561,10,100]，最长完美子集为[3,9,81,6561]，返回值为4

内容的提问来源于stack exchange，提问作者pensee123