题目描述

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

样例

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

输入：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]

输入：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]

输入：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

枚举 + 二分

对于类型1

• 1、对两个数组进行从小到大排序
• 2、在nums1[]中枚举所有的元素nums[i]，用t记录nums1[i] * nums1[i]
• 3、在nums2[]中找到两个不同位置的数满足t == nums[j] * nums[k]，即再枚举nums[j]，通过二分找出nums[k]所在的区间[l, r]，因此当前满足情况的k的个数有r - l + 1个

类型2同理

时间复杂度 $O(n^2logm + m^2logn)$

Java 代码

class Solution {
    static int get(int[] nums1, int[] nums2)
    {
        int n = nums1.length, m = nums2.length;
        int res = 0;
        for(int i = 0;i < n;i ++)
        {
            long t = (long)nums1[i] * nums1[i];
            for(int j = 0;j < m - 1;j ++)
            {
                int l = j + 1, r = m - 1;
                while(l < r)
                {
                    int mid = l + r >> 1;
                    if((long)nums2[j] * nums2[mid] >= t) r = mid;
                    else l = mid + 1;
                }
                if((long)nums2[j] * nums2[l] != t) continue;//说明找不到
                int left = l;
                l = j + 1; r = m - 1;
                while(l < r)
                {
                    int mid = l + r + 1 >> 1;
                    if((long)nums2[j] * nums2[mid] <= t) l = mid;
                    else r = mid - 1;
                }
                int right = l;
                res += right - left + 1;
            }
        }
        return res;
    }
    public int numTriplets(int[] nums1, int[] nums2) {
        Arrays.sort(nums1); Arrays.sort(nums2);
        return get(nums1, nums2) + get(nums2, nums1);
    }
}

算法2

对于类型1

• 1、先用哈希表将nums1[]数组中的所有数的平方存起来，即存nums1[i] * nums1[i]，并记录nums1[i] * nums1[i]出现了多少次
• 2、用两个指针j和k枚举nums2[]数组中不同位置的元素，若nums2[j] * nums2[k] 值在哈希表中存在，则加上nums2[j] * nums2[k]值在哈希表中的次数

类型2同理

时间复杂度 $O(n^2 + m^2)$

Java 代码

class Solution {
    static int get(int[] nums1, int[] nums2)
    {
        HashMap<Long, Integer> map = new HashMap<Long, Integer>();
        int n = nums1.length, m = nums2.length;
        for(int i = 0;i < n;i ++) 
        {
            long t = (long)nums1[i] * nums1[i];
            map.put(t, map.getOrDefault(t, 0) + 1);
        }
        int res = 0;
        for(int i = 0;i < m;i ++)
            for(int j = i + 1;j < m;j ++)
            {
                long t = (long)nums2[i] * nums2[j];
                if(map.containsKey(t))
                {
                    res += map.get(t);
                }
            }

        return res;
    }
    public int numTriplets(int[] nums1, int[] nums2) {
        return get(nums1, nums2) + get(nums2, nums1);
    }
}