难度: Medium
给你一个整数数组 nums 。如果 nums 的子序列满足下述条件，则认为该子序列是一个 方波 ：
2 ，并且返回 nums 中 最长方波 的长度，如果不存在 方波 则返回 -1 。
子序列 也是一个数组，可以由另一个数组删除一些或不删除元素且不改变剩余元素的顺序得到。
示例 1 ：
输入：nums = [4,3,6,16,8,2] 输出：3 解释：选出子序列 [4,16,2] 。排序后，得到 [2,4,16] 。 - 4 = 2 * 2. - 16 = 4 * 4. 因此，[4,16,2] 是一个方波. 可以证明长度为 4 的子序列都不是方波。
示例 2 ：
输入：nums = [2,3,5,6,7] 输出：-1 解释：nums 不存在方波，所以返回 -1 。
提示：
2 <= nums.length <= 1052 <= nums[i] <= 105运行时间: 97 ms
内存: 32.3 MB
class Solution:
def longestSquareStreak(self, nums: List[int]) -> int:
s = set(nums)
ans = -1
for x in s:
cnt = 0
while x in s:
x *= x
cnt += 1
if cnt >= 2:
ans = max(ans, cnt)
return ans
本题解的思路是首先将数组转换为集合，以去除重复元素。然后遍历集合中的每个元素，对于每个元素 x，检查 x 的平方是否在集合中。如果在，就继续检查 x 的平方的平方，以此类推，直到找不到为止。这样可以找到以 x 开头的最长方波的长度。最后返回所有方波中的最大长度。
时间复杂度: O(n log n)
空间复杂度: O(n)
class Solution:
def longestSquareStreak(self, nums: List[int]) -> int:
s = set(nums) # 转换为集合去重
ans = -1 # 初始化最长方波长度为 -1
for x in s: # 遍历集合中的每个元素
cnt = 0 # 初始化当前方波长度为 0
while x in s: # 检查 x 的平方是否在集合中
x *= x # 计算 x 的平方
cnt += 1 # 增加方波长度
if cnt >= 2: # 如果方波长度至少为 2
ans = max(ans, cnt) # 更新最长方波长度
return ans # 返回最长方波长度
将数组转换为集合以去除重复元素不会影响最终结果，因为方波的定义与元素的不同次方值有关，而不是元素的出现次数。每个元素不论出现多少次，其平方值不变。因此，即使原数组中有重复元素，这些重复元素的平方也会相同，不会构成更长的方波。集合的使用是为了方便查找元素是否存在，提高效率。
题解中确实未提及数字溢出的问题。在实际实现时，特别是在使用像Python这样的语言时，通常不需要处理整数溢出，因为Python的int类型可以处理非常大的整数。然而，在其他语言中，如C++或Java，应当考虑溢出的可能性，可以通过使用长整型（long或BigInteger）来避免溢出，或者在每次计算平方前检查x是否大于类型可存储的最大平方根，以防止溢出。
使用x *= x来计算平方可能会忽略掉一些有效的方波序列。例如，如果一个元素和它的平方之间存在其他数字的平方，这些序列将不会被考虑。这种方法只能检查连续平方的存在，而忽视了可能存在于集合中的间断平方。为了捕捉所有可能的方波序列，算法需要修改以检查集合中任何元素的平方，而不仅仅是连续的平方。
是的，最长方波长度初始化为-1是为了处理数组中不存在任何方波的情况。然而，在实际实现中，应当在返回结果前检查是否有至少一个方波被发现，如果没有任何方波（ans仍为-1），则应当返回0或其他标志值，表明没有找到有效的方波。这样可以确保算法正确表达方波不存在的情况。