[哈希表][排序+双指针]leetcode1726:同积元组(medium)

题目:
[哈希表][排序+双指针]leetcode1726:同积元组(medium)
[哈希表][排序+双指针]leetcode1726:同积元组(medium)


题解:

思路1:超时啦555

  • 排序+双指针,代码模拟《四数之和》,只不过指针 j 需要从后向前遍历,因为这样 a[i]*a[j] 才能被中间相对较小的数字相乘获得相同的积。若指针 j 也从头开始遍历的话,双指针的乘积必然大于 a[i]*a[j] 这样肯定是不行的(因为数组已经排序的过了,所以双指针的运算结果更大)。

思路2:

  • hashmap存储所有的两数之积,标准的四元组必定是相同的两数之积中两两组合,如乘积为 x 的个数为 y,那么标准的四元组的个数为 y*(y-1)/2,最后结果还需要乘以 8 表示打乱顺序之后的所有四元组。

代码如下:

// 思路1代码
class Solution {
public:
    int tupleSameProduct(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int res=0,n=nums.size();
        for(int i=0;i<n-3;++i)
        {
            for(int j=n-1;j>i+2;j--)
            {
                int l=i+1,r=j-1;
                while(l<r)
                {
                    int x=nums[i]*nums[j],y=nums[l]*nums[r];
                    if(y>x)r--;
                    else if(y<x)l++;
                    else{
                        res+=8;
                        l++,r--;
                    }
                }
            }
        }
        return res;
    }
};
// 思路2代码
class Solution {
public:
    // 哈希表:统计数组中两个不同数字的乘积的个数,其中标准的四元组的个数为两个数字相同乘积的两两组合,即乘积为x的个数y中选2个,y*(y-1)/2
    int tupleSameProduct(vector<int>& a) {
        int n=a.size();
        unordered_map<int,int> mp;
        for(int i=0;i<n;++i)
            for(int j=i+1;j<n;++j)
                mp[a[i]*a[j]]++;
        int res=0;
        for(auto [x,y]:mp)
            res+=y*(y-1)/2*8;
        return res;
    }
};
上一篇:umi-request 网络请求之路


下一篇:羽未「umi」