数的平方等于两数乘积的方法数Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

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

# 思路

Map

# 解法

class Solution {
    public int numTriplets(int[] nums1, int[] nums2) {
        Map<Integer, Integer> cntmap1 = new HashMap<>();
        Map<Integer, Integer> cntmap2 = new HashMap<>();
        for(int num : nums1) {
            cntmap1.put(num, cntmap1.getOrDefault(num, 0)+1);
        }
        for(int num : nums2) {
            cntmap2.put(num, cntmap2.getOrDefault(num, 0)+1);
        }
        return getNum(cntmap1, cntmap2) + getNum(cntmap2, cntmap1);   
    }
    
    private int getNum(Map<Integer, Integer> cntmap1, Map<Integer, Integer> cntmap2) {
        int ans = 0;
        List<Integer> list = new ArrayList<Integer>(cntmap1.keySet());
        Map<Long, Integer> map = new HashMap<>();
        for(int key : cntmap2.keySet()) {
            map.put((long)key*key, key);
        }
        int n = list.size();
        for(int i=0; i<n; i++) {
            for(int j=i; j<n; j++) {
                int num = list.get(i);
                if(i == j && cntmap1.get(num) == 1) continue;
                long target = (long)num * list.get(j);
                if(map.get(target) == null) continue;
                if(i == j) {
                    int cnt = cntmap1.get(num);
                    ans += cnt*(cnt-1)/2*(cntmap2.get(map.get(target)));
                } else {
                    ans += cntmap1.get(num)*cntmap1.get(list.get(j))*(cntmap2.get(map.get(target)));
                }
                
            }
        }
        return ans;
    }
}

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

# 总结

分析出几种情况，然后分别对各个情况实现

#Java