码农知识堂 - 1000bd
  •   Python
  •   PHP
  •   JS/TS
  •   JAVA
  •   C/C++
  •   C#
  •   GO
  •   Kotlin
  •   Swift

  • 【Leetcode】【中等】1726.同积元组

    力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能，轻松拿下世界 IT 名企 Dream Offer。icon-default.png?t=N7T8https://leetcode.cn/problems/tuple-with-same-product/

    给你一个由 不同 正整数组成的数组 nums ，请你返回满足 a * b = c * d 的元组 (a, b, c, d) 的数量。其中 a、b、c 和 d 都是 nums 中的元素，且 a != b != c != d 。

    示例 1：

    输入：nums = [2,3,4,6]
输出：8
解释：存在 8 个满足题意的元组：
(2,6,3,4) , (2,6,4,3) , (6,2,3,4) , (6,2,4,3)
(3,4,2,6) , (4,3,2,6) , (3,4,6,2) , (4,3,6,2)

    示例 2：

    输入：nums = [1,2,4,5,10]
输出：16
解释：存在 16 个满足题意的元组：
(1,10,2,5) , (1,10,5,2) , (10,1,2,5) , (10,1,5,2)
(2,5,1,10) , (2,5,10,1) , (5,2,1,10) , (5,2,10,1)
(2,10,4,5) , (2,10,5,4) , (10,2,4,5) , (10,2,5,4)
(4,5,2,10) , (4,5,10,2) , (5,4,2,10) , (5,4,10,2)

    自己的思路

    一开始真的去定义了一个四元组，做完超时了，后面改成HashMap，这里把四元组的代码贴出来，当做复习了。。。

    1. public static class FourTuple {
    2.         public Object first;
    3.         public Object second;
    4.  
    5.         public Object third;
    6.  
    7.         public Object fourth;
    8.  
    9.         public FourTuple() {
    10.         }
    11.  
    12.         public FourTuple(Object first, Object second, Object third, Object fourth) {
    13.             this.first = first;
    14.             this.second = second;
    15.             this.third = third;
    16.             this.fourth = fourth;
    17.         }
    18.  
    19.         @Override
    20.         public String toString() {
    21.             return "[" + this.first + "," + this.second + "," + this.third + "," + this.fourth + "]";
    22.         }
    23.     }
      24.  

      比较正确的思路
       

      使用两层循环遍历数组nums，计算nums[i]与nums[j]的乘积，将其当做key，value为key出现的次数。如果原来没有这个key的，就放入1；如果原来有这个key的，就在它的基础上加1。
       

      这段代码如下：
       

      1.         for (int i = 0; i < len; i++) {
      2.             int mul_result;
      3.             for (int j = i + 1; j < len; j++) {
      4.                 mul_result = nums[i] * nums[j];
      5.                 hashMap.put(mul_result, hashMap.getOrDefault(mul_result, 0) + 1);
      6.             }
      7.         }
       

      如果value>=2的话，就证明存在有乘积相等的元组。
       

      因为这段代码超时了，这里我发现"value与乘积相等元组个数之间"的关系，例如value=3，则有2+1=3个符合条件的元组，便使用了if语句判断value>=2，利用以下式子计算元组个数：
       

      1. public static int cal(int x) {
      2.         int sum = 0;
      3.         x = x - 1;
      4.         while (x >= 1) {
      5.             sum += x;
      6.             x--;
      7.         }
      8.         return sum;
      9. }
      10.  
      11. public static int tupleSameProduct(int[] nums) {
      12.     ...
      13.     int res = 0;
      14.     for (Map.Entry entry : hashMap.entrySet()) {
      15.         res += cal(entry.getValue());
      16.     }
      17.     return res;
      18. }
       

       

      力扣官方题解 
       

      力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能，轻松拿下世界 IT 名企 Dream Offer。icon-default.png?t=N7T8https://leetcode.cn/problems/tuple-with-same-product/solutions/2470655/tong-ji-yuan-zu-by-leetcode-solution-7yyy/应该是3 * (3 - 1) / 2 = 3，而不是2 + 1 = 3。前者时间复杂为O(1)，后者需要遍历，时间复杂度为O(n)。一个元组有8种不一样的排序，如下所示
       

       
 
      (2,6,3,4) , (2,6,4,3) , (6,2,3,4) , (6,2,4,3) (3,4,2,6) , (4,3,2,6) , (3,4,6,2) , (4,3,6,2)
       

       

      所以每个元组就有n * (n - 1) / 2 * 8 = n * (n - 1) * 4。
       

      代码
       

      1. class Solution {
      2.     public int tupleSameProduct(int[] nums) {
      3.         int len = nums.length;
      4.         HashMap hashMap = new HashMap<>();
      5.         int res = 0;
      6.         for (int i = 0; i < len; i++) {
      7.             int mul_result;
      8.             for (int j = i + 1; j < len; j++) {
      9.                 mul_result = nums[i] * nums[j];
      10.                 hashMap.put(mul_result, hashMap.getOrDefault(mul_result, 0) + 1);
      11.             }
      12.         }
      13.     
      14.         for (Integer v : hashMap.values()) {
      15.             res += v * (v - 1) * 4;
      16.         }
      17.         return res;
      18.     }
      19. }
       

      
                
                    
                

                
    24. 

                    相关阅读:
      
                    
用友一面面经                            
      
按键中断实验                            
      
每个前端都应该掌握的7个代码优化的小技巧                            
      
Spring.事务实现方式和源码分析                            
      
Spark Core之RDD                            
      
汽车信息安全导图                            
      
【SpringBoot】秒杀业务：redis+拦截器+自定义注解+验证码简单实现限流                            
      
Mybatis——拦截器Interceptor                            
      
ML/DL2022面试必备500知识点-《机器和深度学习纲要》免费分享                            
      
六安RapidSSL泛域名https能保护几个域名                            
      
                          
                
      25. 
                
    25. 
                    原文地址：https://blog.csdn.net/have_to_be/article/details/134000737
                
      26. 

            
        

        
      
            
        
                
      • 
                    最新文章
                
        • 
                
      • 
                    
攻防演习之三天拿下官网站群                            
        
数据安全治理学习——前期安全规划和安全管理体系建设                            
        
企业安全 | 企业内一次钓鱼演练准备过程                            
        
内网渗透测试 | Kerberos协议及其部分攻击手法                            
        
0day的产生 | 不懂代码的"代码审计"                            
        
安装scrcpy-client模块av模块异常，环境问题解决方案                            
        
leetcode hot100【LeetCode 279. 完全平方数】java实现                            
        
OpenWrt下安装Mosquitto                            
        
AnatoMask论文汇总                            
        
【AI日记】24.11.01 LangChain、openai api和github copilot                            
        
                            
                
        • 
            
      

            
        
                
      • 
                    热门文章
                
        • 
                
      • 
                    
十款代码表白小特效 一个比一个浪漫 赶紧收藏起来吧！！！                            
        
奉劝各位学弟学妹们，该打造你的技术影响力了！                            
        
五年了，我在 CSDN 的两个一百万。                            
        
Java俄罗斯方块，老程序员花了一个周末，连接中学年代！                            
        
面试官都震惊，你这网络基础可以啊！                            
        
你真的会用百度吗？我不信 — 那些不为人知的搜索引擎语法                            
        
心情不好的时候，用 Python 画棵樱花树送给自己吧                            
        
通宵一晚做出来的一款类似CS的第一人称射击游戏Demo！原来做游戏也不是很难，连憨憨学妹都学会了！                            
        
13 万字 C 语言从入门到精通保姆级教程2021 年版                            
        
10行代码集2000张美女图，Python爬虫120例，再上征途                            
        
                            
                
        • 
            
      

        
      
    




    
    
    
    

      
    
      
        
      
            
      
                
      
                    Copyright © 2022 侵权请联系2656653265@qq.com   
                    京ICP备2022015340号-1
                
      
                
      
                    正则表达式工具
                    cron表达式工具
                    密码生成工具
                
      
                
      
                    
                    
      京公网安备 11010502049817号