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

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:25 2023-09-13 16:06:25 Updated    

给你两个整数数组 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

方法一：哈希表

直观的做法是暴力枚举符合规则的三元组的数目。寻找类型 1 的三元组时，首先遍历数组 nums}_1，对于其中的每个元素，遍历数组 nums}_2 中的每一对元素，找到符合规则的三元组的数目。然后使用同样的方法寻找类型 2 的三元组。假设数组 nums}_1 和 nums}_2 的长度分别为 m 和 n，则暴力法的时间复杂度为 O(mn^2+m^2n)。

由于每个数组都可能包含重复元素，因此暴力法可能有大量重复计算，可以通过避免重复计算的做法降低时间复杂度。

考虑类型 1 的三元组 (i,j,k)，满足 nums}_1[i]^2==\textit{nums}_2[j] \times \textit{nums}_2[k]，其中 0 \le i \le m 和 0 \le j < k < n。如果 nums}_1 中有和 nums}_1[i] 重复的元素，nums}_2 中有和 nums}_2[j] 以及 nums}_2[k] 重复的元素，则用重复元素替换对应的数字，规则仍然成立。因此，符合规则的三元组的数目与两个数组中的每个元素的出现次数有关。

使用两个哈希表分别存储数组 nums}_1 中的每个元素出现的次数和数组 nums}_2 中的每个元素出现的次数，并分别使用集合 set}_1 和 set}_2 存储数组 nums}_1 中的元素和数组 nums}_2 中的元素，在遍历元素时可以遍历两个集合，避免重复访问相同元素。

寻找类型 1 的三元组时，遍历集合 set}_1 中的每个元素，对于每个元素，遍历集合 set}_2 找到类型 1 的三元组个数。对于集合 set}_1 中的元素 num}_1，需要在集合 set}_2 中寻找到所有的二元组 (\textit{num}_2,\textit{num}_3)，满足 num}_2 \le \textit{num}_3 且 num}_1^2==\textit{num}_2 \times \textit{num}_3。

假设 num}_1 在数组 nums}_1 中出现的次数是 count}_1，num}_2 和 num}_3 在数组 nums}_2 中出现的次数分别是 count}_2 和 count}_3，则这三个数对应的类型 1 的三元组的数目计算方式如下：

  • 如果 num}_2==\textit{num}_3，则三元组的数目是 count}_1 \times \textit{count}_2 \times (\textit{count}_2 - 1) / 2；

  • 如果 num}_2<\textit{num}_3，则三元组的数目是 count}_1 \times \textit{count}_2 \times \textit{count}_3。

在计算类型 1 的三元组数目之后，可以使用同样的方法计算类型 2 的三元组数目。

[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    public int numTriplets(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map1 = new HashMap<Integer, Integer>();
        Map<Integer, Integer> map2 = new HashMap<Integer, Integer>();
        for (int num : nums1) {
            int count = map1.getOrDefault(num, 0) + 1;
            map1.put(num, count);
        }
        for (int num : nums2) {
            int count = map2.getOrDefault(num, 0) + 1;
            map2.put(num, count);
        }
        return getTriplets(map1, map2) + getTriplets(map2, map1);
    }

    public int getTriplets(Map<Integer, Integer> map1, Map<Integer, Integer> map2) {
        int triplets = 0;
        Set<Integer> set1 = map1.keySet();
        Set<Integer> set2 = map2.keySet();
        for (int num1 : set1) {
            int count1 = map1.get(num1);
            long square = (long) num1 * num1;
            for (int num2 : set2) {
                if (square % num2 == 0 && square / num2 <= Integer.MAX_VALUE) {
                    int num3 = (int) (square / num2);
                    if (num2 == num3) {
                        int count2 = map2.get(num2);
                        int curTriplets = count1 * count2 * (count2 - 1) / 2;
                        triplets += curTriplets;
                    } else if (num2 < num3 && set2.contains(num3)) {
                        int count2 = map2.get(num2), count3 = map2.get(num3);
                        int curTriplets = count1 * count2 * count3;
                        triplets += curTriplets;
                    }
                }
            }
        }
        return triplets;
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    int getTriplets(const unordered_map<int, int>& map1, const unordered_map<int, int>& map2) {
        int triplets = 0;
        for (const auto& [num1, count1]: map1) {
            long long square = (long long)num1 * num1;
            for (const auto& [num2, count2]: map2) {
                if (square % num2 == 0 && square / num2 <= INT_MAX) {
                    int num3 = square / num2;
                    if (num2 == num3) {
                        int curTriplets = count1 * count2 * (count2 - 1) / 2;
                        triplets += curTriplets;
                    } else if (num2 < num3 && map2.count(num3)) {
                        int count3 = map2.at(num3);
                        int curTriplets = count1 * count2 * count3;
                        triplets += curTriplets;
                    }
                }
            }
        }
        return triplets;
    }

    int numTriplets(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> map1, map2;
        for (int num: nums1) {
            ++map1[num];
        }
        for (int num: nums2) {
            ++map2[num];
        }
        return getTriplets(map1, map2) + getTriplets(map2, map1);
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
        def getTriplets(map1: Counter, map2: Counter):
            triplets = 0
            for num1, count1 in map1.items():
                square = num1 * num1
                for num2, count2 in map2.items():
                    if square % num2 == 0:
                        num3 = square // num2
                        if num2 == num3:
                            curTriplets = count1 * count2 * (count2 - 1) // 2
                            triplets += curTriplets
                        elif num2 < num3 and num3 in map2:
                            count3 = map2[num3]
                            curTriplets = count1 * count2 * count3
                            triplets += curTriplets
            return triplets

        map1 = collections.Counter(nums1)
        map2 = collections.Counter(nums2)
        return getTriplets(map1, map2) + getTriplets(map2, map1)

复杂度分析

  • 时间复杂度：O(mn)，其中 m 和 n 分别是数组 nums}_1 和 nums}_2 的长度。
    遍历两个数组，分别将两个数组中的每个元素出现的次数存入两个哈希表，时间复杂度是 O(m+n)；
    寻找类型 1 的三元组，需要不重复地遍历数组 nums}_1 中的每个元素，并对每个元素不重复地遍历数组 nums}_2 中的每个元素，时间复杂度是 O(mn)；
    寻找类型 2 的三元组，时间复杂度也是 O(mn)。
    因此总时间复杂度是 O(mn)。

  • 空间复杂度：O(m+n)，其中 m 和 n 分别是数组 nums}_1 和 nums}_2 的长度。空间复杂度取决于两个哈希表，两个哈希表的大小都不会超过对应的数组的长度。

 Comments
On this page
1577-数的平方等于两数乘积的方法数