老师，能不能稍微说一下3Sum这道题用查找表解决的思路？

Question

对撞指针的思路我已经accepted了

而使用查找表的方式，我通过了311个测试用例，就差最后两个超长的测试用例，不通过的原因是超时。但是我想不出有什么优化的思路，我觉得我的思路已经没什么问题了。。。

Answer 1

liuyubobobo 2018-02-06 18:37:42

可以试一下这个思路：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0015%203Sum/cpp-3Sum/main1.cpp

• 提问者 ShiveryMoon #1

  果然还是先需要排序吗。。。我一直没有排序，用一种很神奇的方式在消除冗余解，代码是没有问题的，只是用时太长

• liuyubobobo 回复 提问者 ShiveryMoon #2

  神奇的方式是什么？目测神奇的方式去除冗余解不是O(1)的，所以整个程序时间复杂度不是O(n^2)：）

• 提问者 ShiveryMoon 回复 liuyubobobo #3

  我看看能不能说清楚吧。。
  首先做一个统计所有出现字符和每个字符出现次数的map。
  for i:
      如果map[i]>0：
          在map里将i的出现次数减一
          然后复制一份map2=map用于内层循环
          for j：
              如果map2[j]>0：
                  map2中j的出现次数减一
                  因为i是固定的，如果i+j+(0-i-j)=0，那么同一组解(j,0-i-j)是唯一的
                  所以一旦找到一组(j,k),就让map2[j]=0,map2[0-i-j]=0
      如果在内层循环里找到一组解，那么，map[i]=0，相当于直接在map中删掉i

点开查看后面4条评论