3sum

这道题看似很简单，但是容易超时。

• 首先排序
• 然后一个首指针，一个尾指针，前后搜索。
• 时间复杂度O(N*N)

3sumClosest

• 这道题目与3Sum方法相似，只需每次判断是否距离target最近即可。
• 时间复杂度O(N*N)

4Sum

• 最简单的方法是按照3Sum的思路，再添加一次循环，时间的复杂度为O(N*N*N),但是无论怎么优化，提交之后老是超时。而同样的方法C++可以提交成功，说明python的运行速度偏慢。
• 借鉴南郭子廭的思路，采用哈希的思路，采用空间换时间的。首先建立一个字典dict，字典的key值为数组中每两个元素的和，每个key对应的value为这两个元素的下标组成的元组，元组不一定是唯一的。
• 如对于num=[1,2,3,2]来说，dict={3:[(0,1),(0,3)], 4:[(0,2),(1,3)], 5:[(1,2),(2,3)]}。
• 由于需要去重，这里选用set()类型的数据结构，即无序无重复元素集。最后将每个找出来的解(set()类型)转换成list类型输出即可。
• python的set和其他语言类似, 是一个无序不重复元素集, 基本功能包括关系测试和消除重复元素.
• 时间复杂度为O(N*N+N*N)=O(N*N)

代码

---

有志者事竟成