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 <= 10^5
  • 2 <= nums[i] <= 10^5

提示：

  • 在给定约束下，最长平方连续子序列的长度最多为 5。
  • 将 nums 的元素存储在集合中以快速检查元素是否存在。

解题思路

解题思路

这道题要求找到数组中最长的平方连续子序列。我们需要理解什么是平方连续子序列：排序后的子序列中每个元素都是前一个元素的平方。

方法分析

哈希表 + 动态规划 （推荐）：

  1. 将数组元素存入哈希集合，便于 O(1) 时间检查元素是否存在
  2. 对于每个数字，尝试以它作为平方连续子序列的起点
  3. 不断计算下一个平方值，如果存在就继续扩展序列
  4. 记录所有序列的最大长度

关键优化点：

  • 由于约束条件 nums[i] <= 10^5，最长的平方连续子序列长度最多为 5（因为 2^16 > 10^5）
  • 只需要从较小的数开始搜索，避免重复计算
  • 使用哈希表标记已访问的元素，避免重复计算同一条链

时间复杂度分析： 虽然看起来是嵌套循环，但每个元素最多被访问常数次（作为链的起点或中间节点），所以总时间复杂度是 O(n)。

代码实现

class Solution {
public:
    int longestSquareStreak(vector<int>& nums) {
        unordered_set<int> numSet(nums.begin(), nums.end());
        int maxStreak = -1;
        
        for (int num : nums) {
            if (numSet.count(num) == 0) continue; // 已被访问过
            
            int current = num;
            int streak = 1;
            
            // 向前查找更小的起点
            int sqrt_val = sqrt(current);
            if (sqrt_val * sqrt_val == current && numSet.count(sqrt_val)) {
                continue; // 不是真正的起点
            }
            
            // 从当前数开始构建平方序列
            while (true) {
                numSet.erase(current); // 标记为已访问
                long long next = (long long)current * current;
                if (next > 100000 || numSet.count(next) == 0) break;
                current = next;
                streak++;
            }
            
            if (streak >= 2) {
                maxStreak = max(maxStreak, streak);
            }
        }
        
        return maxStreak;
    }
};

class Solution:
    def longestSquareStreak(self, nums: List[int]) -> int:
        num_set = set(nums)
        max_streak = -1
        
        for num in nums:
            if num not in num_set:  # 已被访问过
                continue
            
            current = num
            streak = 1
            
            # 向前查找更小的起点
            sqrt_val = int(current ** 0.5)
            if sqrt_val * sqrt_val == current and sqrt_val in num_set:
                continue  # 不是真正的起点
            
            # 从当前数开始构建平方序列
            while True:
                num_set.discard(current)  # 标记为已访问
                next_val = current * current
                if next_val > 100000 or next_val not in num_set:
                    break
                current = next_val
                streak += 1
            
            if streak >= 2:
                max_streak = max(max_streak, streak)
        
        return max_streak

public class Solution {
    public int LongestSquareStreak(int[] nums) {
        HashSet<int> numSet = new HashSet<int>(nums);
        int maxStreak = -1;
        
        foreach (int num in nums) {
            if (!numSet.Contains(num)) continue; // 已被访问过
            
            int current = num;
            int streak = 1;
            
            // 向前查找更小的起点
            int sqrtVal = (int)Math.Sqrt(current);
            if (sqrtVal * sqrtVal == current && numSet.Contains(sqrtVal)) {
                continue; // 不是真正的起点
            }
            
            // 从当前数开始构建平方序列
            while (true) {
                numSet.Remove(current); // 标记为已访问
                long next = (long)current * current;
                if (next > 100000 || !numSet.Contains((int)next)) break;
                current = (int)next;
                streak++;
            }
            
            if (streak >= 2) {
                maxStreak = Math.Max(maxStreak, streak);
            }
        }
        
        return maxStreak;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestSquareStreak = function(nums) {
    const numSet = new Set(nums);
    let maxStreak = 0;
    
    for (let num of nums) {
        let current = num;
        let streak = 1;
        
        while (numSet.has(current * current)) {
            current = current * current;
            streak++;
        }
        
        maxStreak = Math.max(maxStreak, streak);
    }
    
    return maxStreak >= 2 ? maxStreak : -1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(n)

说明：

  • 时间复杂度：虽然有嵌套循环，但每个元素最多被访问常数次，由于数值范围限制，平方序列长度最多为5，所以总时间复杂度为 O(n)
  • 空间复杂度：使用哈希集合存储所有元素，空间复杂度为 O(n)