4 sum

2 pointer 解法

4 sum的话可以转换为3 sum, 再2 sum解法。这样的话时间复杂度是O(n^3).

hash 解法

4 sum其实有更快的解法，可以达到O(n^2).

  1. 将array中的所有pair存到一个hashtable中
  2. key是pair的和，value是一个list,每个element是一个pair
  3. 这一步骤的时间复杂度是O（n^2)
  4. 然后就可以像2sum的hash做法一样解决了

注意点

这个解法有很多的细节要处理，如何去重

  • 存的pair应该存index,这样在两个pair的时候比较容易判断是否重合

http://codeganker.blogspot.com/2014/04/4sum-leetcode.html http://www.cnblogs.com/TenosDoIt/p/3649607.html