使用hashmap优化时间复杂度，leetcode1577

1577. 数的平方等于两数乘积的方法数

已解答

中等

相关标签

相关企业

提示

给你两个整数数组 nums1 和 nums2 ，请你返回根据以下规则形成的三元组的数目（类型 1 和类型 2 ）：

• 类型 1：三元组 (i, j, k) ，如果 nums1[i]2 == nums2[j] * nums2[k] 其中 0 <= i < nums1.length 且 0 <= j < k < nums2.length
• 类型 2：三元组 (i, j, k) ，如果 nums2[i]2 == nums1[j] * nums1[k] 其中 0 <= i < nums2.length 且 0 <= j < k < nums1.length

示例 1：

输入：nums1 = [7,4], nums2 = [5,2,8,9]
输出：1
解释：类型 1：(1,1,2), nums1[1]^2 = nums2[1] * nums2[2] (4^2 = 2 * 8)

示例 2：

输入：nums1 = [1,1], nums2 = [1,1,1]
输出：9
解释：所有三元组都符合题目要求，因为 1^2 = 1 * 1
类型 1：(0,0,1), (0,0,2), (0,1,2), (1,0,1), (1,0,2), (1,1,2), nums1[i]^2 = nums2[j] * nums2[k]
类型 2：(0,0,1), (1,0,1), (2,0,1), nums2[i]^2 = nums1[j] * nums1[k]

示例 3：

输入：nums1 = [7,7,8,3], nums2 = [1,2,9,7]
输出：2
解释：有两个符合题目要求的三元组
类型 1：(3,0,2), nums1[3]^2 = nums2[0] * nums2[2]
类型 2：(3,0,1), nums2[3]^2 = nums1[0] * nums1[1]

示例 4：

输入：nums1 = [4,7,9,11,23], nums2 = [3,5,1024,12,18]
输出：0
解释：不存在符合题目要求的三元组

提示：

• 1 <= nums1.length, nums2.length <= 1000
• 1 <= nums1[i], nums2[i] <= 10^5

 

 解决思路：直观来看，直接暴力遍历算法也是正确的，然而时间复杂度比较高O(n^3),根据leetcode的规律，只有数据规模小于100的时候，才能使用这个复杂度的算法。所以，需要优化，这里使用哈希表记录每个数组的平方值，然后统计第二个数组中nums1[j] * nums1[k] 是否==第一个数组中的平方值，有的话就相加，没有就继续。复杂度可以降低为O(n^2),通过测试。

class Solution {
public:
    int numTriplets(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        int m = nums2.size();
        unordered_map<long, int> square_count1;
        unordered_map<long, int> square_count2;
        int count = 0;
        // 计算 nums1 和 nums2 每个元素的平方，并存储在哈希表中
        for (int num : nums1) {
            long square = (long)num * num;
            square_count1[square]++;
        }
        for (int num : nums2) {
            long square = (long)num * num;
            square_count2[square]++;
        }
        // 枚举 nums1 的所有可能的两个元素的乘积
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                long product = (long)nums1[i] * nums1[j];
                // 检查 product 的平方是否在哈希表中
                count+=square_count2[product];
            }
        }
        // 枚举 nums2 的所有可能的两个元素的乘积
        for (int i = 0; i < m; ++i) {
            for (int j = i + 1; j < m; ++j) {
                long product = (long)nums2[i] * nums2[j];
                // // 检查 product 的平方是否在哈希表中
                count+=square_count1[product];
            }
        }
        return count;
    }
};

执行用时分布

135ms

击败34.58%使用 C++ 的用户

消耗内存分布

37.60MB

击败9.34%使用 C++ 的用户

官方题解给了更快的算法。随着AI的大模型普及，以后程序员可能会成为历史，可能以后编程就是提示和应用工程师。但是算法的思想和解决问题的能力，这个暂时是AI无法替代的。