文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給你兩個整數(shù)數(shù)組 nums1 和 nums2 ，請你返回根據(jù)以下規(guī)則形成的三元組的數(shù)目（類型 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

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/number-of-ways-where-square-of-number-is-equal-to-product-of-two-numbers
著作權(quán)歸領(lǐng)扣網(wǎng)絡所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 解題

• 雙指針遍歷，注意有相同的數(shù)字滿足時，要左右相乘

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結(jié)束{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;//左右相乘}}}}} };

20 ms 11.2 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關(guān)注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 1577. 数的平方等于两数乘积的方法数（双指针）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。