LeetCode 1577. 数的平方等于两数乘积的方法数（双指针）

示例 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

class Solution {
	int s;
public:
    int numTriplets(vector<int>& nums1, vector<int>& nums2) {
    	s = 0;
    	process(nums1, nums2);
    	process(nums2, nums1);
    	return s;
    }
    void process(vector<int>& nums1, vector<int>& nums2) 
    {
    	long long n1 = nums1.size(), n2 = nums2.size(), t1, t2, i, j, k;
    	sort(nums2.begin(), nums2.end());//后者排序
    	for(i = 0; i < n1; i++)
    	{
    		j = 0, k = n2-1;//双指针
    		t1 = (long long)nums1[i]*nums1[i];
    		while(j < k)
    		{
    			t2 = (long long)nums2[j]*nums2[k];
    			if(t1 > t2)
    				j++;
    			else if(t1 < t2)
    				k--;
    			else//相等
    			{
    				if(nums2[j] == nums2[k])//相等，直接Cn2结束
    				{
    					s += (k-j+1)*(k-j)/2;
    					break;
    				}
    				else
    				{
    					int l = nums2[j], r = nums2[k];
    					int ct1 = 0, ct2 = 0;
    					while(nums2[j] == l)
    					{
    						ct1++, j++;
    					}
    					while(nums2[k] == r)
    					{
    						ct2++, k--;
    					}
    					s += ct1*ct2;//左右相乘
    				}
    			}
    		}
    	}
    }
};