3Sum Time Limit Exceeded HashMap 优化过程-白红宇的个人博客

发布日期：2021-08-19 11:10:02 浏览次数：8 分类：技术文章

本文共 2855 字，大约阅读时间需要 9 分钟。

　　昨晚，在做leetcode上的3Sum题目时，感觉这道题目和2Sum很像，当时解决2Sum时，思路如下：

用HashMap的key存储 num[i]，value存储下标 i，之后在遍历数组num时，判断target-num[i]是否在HashMap的key中，大致解题思路是这样的。于是我决定继续用这个思路解决3Sum问题。思路如下：

用2层for循环(同理4Sum问题用3层for循环)，Java代码(此段代码Time Limit Exceeded)如下：

public List
     
      
       > threeSum(int[] num) {                Arrays.sort(num);        List
       
        
         > listAll = new ArrayList
         
          
           >(); Map
           
             hm = new HashMap
            
             (); for(int i = 0; i < num.length; i++) { hm.put(num[i], i); } for (int i = 0; i < num.length; i++) { int oneTmp = -num[i]; if (oneTmp < 0) { break; } for (int j = i + 1; j < num.length; j++) { int thirdTmp = oneTmp - num[j]; if (hm.containsKey(thirdTmp) && hm.get(thirdTmp) > j) { List
             
               listTmp = new ArrayList
              
               (); listTmp.add(num[i]); listTmp.add(num[j]); listTmp.add(thirdTmp); if (!listAll.contains(listTmp)) { listAll.add(listTmp); } } } } return listAll; }

上面的这段代码提交时，一直显示Time Limit Exceeded。经过检查，发现问题出现在上面的红色代码处，我是计算了很多重复的triplet后，然后再用listAll的contains判断并去重，这样的操作会占用一定的时间，导致Time Limit Exceeded。

第一次优化：优化第二层for循环的下标j的遍历方法，Java代码(很奇怪的是这段代码第一次提交时Accepted了，之后几次提交都是Time Limit Exceeded)如下：

public List
     
      
       > threeSum(int[] num) {                Arrays.sort(num);        List
       
        
         > listAll = new ArrayList
         
          
           >(); Map
           
             hm = new HashMap
            
             (); for(int i = 0; i < num.length; i++) { hm.put(num[i], i); } for (int i = 0; i < num.length; i++) { int oneTmp = -num[i]; if (oneTmp < 0) { break; } for (int j = i + 1; j < num.length; j++) { int thirdTmp = oneTmp - num[j]; if (hm.containsKey(thirdTmp) && hm.get(thirdTmp) > j) { List
             
               listTmp = new ArrayList
              
               (); listTmp.add(num[i]); listTmp.add(num[j]); listTmp.add(thirdTmp); listAll.add(listTmp); while ((j < num.length - 1) && (num[j] == num[j + 1])) { j ++; } } } } return listAll; }

其实就是把第一段代码中的红色部分，替换成黄色部分。

第二次优化，就是优化第一层for循环的下标 i 的遍历方法，最终Java代码(这次以318ms Accepted了)如下：

public List
     
      
       > threeSum(int[] num) {                Arrays.sort(num);        List
       
        
         > listAll = new ArrayList
         
          
           >(); Map
           
             hm = new HashMap
            
             (); for(int i = 0; i < num.length; i++) { hm.put(num[i], i); } for (int i = 0; i < num.length; i++) { int oneTmp = -num[i]; if (oneTmp < 0) { break; } for (int j = i + 1; j < num.length; j++) { int thirdTmp = oneTmp - num[j]; if (hm.containsKey(thirdTmp) && hm.get(thirdTmp) > j) { List
             
               listTmp = new ArrayList
              
               (); listTmp.add(num[i]); listTmp.add(num[j]); listTmp.add(thirdTmp); listAll.add(listTmp); while ((j < num.length - 1) && (num[j] == num[j + 1])) { j ++; } } } while ((i < num.length - 1) && (num[i] == num[i + 1])) { i ++; } } return listAll; }

其实就是在第二段代码的基础上，再加上面绿色代码。至此，基于HashMap的解决3Sum问题的Java代码优化结束~

转载于:https://www.cnblogs.com/lasclocker/p/4417758.html

转载地址：https://blog.csdn.net/weixin_30924087/article/details/96985327 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：pyspider安装及使用过程中遇到的问题

下一篇：Could not resolve dependencies for project, Failed to read artifact descriptor for

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章