2501.数组中最长的方波

链接：2501.数组中最长的方波
难度：Medium
标签：数组、哈希表、二分查找、动态规划、排序
简介：返回 nums 中 最长方波 的长度，如果不存在 方波 则返回 -1 。

题解 1 - cpp

• 编辑时间：2022-12-11
• 执行用时：244ms
• 内存消耗：105.7MB
• 编程语言：cpp
• 解法介绍：哈希后遍历。

class Solution {
public:
    int longestSquareStreak(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size(), ans = -1;
        unordered_map<int, int> m;
        for (int i = 0; i < n; i++) {
            if (!m.count(nums[i])) m[nums[i]] = i;
        }
        vector<int> dp(n, 1);
        for (int i = 0; i < n; i++) {
            int num = nums[i], prev = sqrt(num);
            //cout << "num = " << num << ", p = " << prev << endl;
            if (prev * prev != num) continue;
            if (!m.count(prev)) continue;
            dp[i] = max(dp[i], dp[m[prev]] + 1);
            //cout << "i = " << i << ", dp = " << dp[i] << endl;
            if (dp[i] > 1) ans = max(ans, dp[i]);
        }
        return ans;
    }
};