Two Sum:
题目： 给定数组返回两个数之和为target的所有组合，每个数只能用一次
思路1：hash table: O(2n)
首先遍历一遍数组记录所有元素出现的次数，key 为元素， value 该元素出现的次数。第二次遍历所有key。检测对于target - key的value是否为0或者不存在(我们可以约定被访问过的key将其value设置为0来避免后面出现重复组合)。 如果 target - key == key 那么key对应的value1必须大于1才可。
思路2： Two Pointer(主流做法)
首先我们对数组进行排序。随后我们设定两个指针i，j分别指向首尾。计算两者的和s, s > target 则 i ++，s < target则j --；否则记录nums[i], nums[j]。重点在出去重复：while i < j and nums[i] == nums[i + 1]：i ++； 同理 while i < j and nums[j] == nums[i - 1]：j ++,随后 j --, i ++;时间复杂度O(nlogn) + O(n)
关键代码如下（python）：
while j < l:
if nums[j] > target:
break
tmp = nums[j] + nums[l]
if tmp == target:
res.append(nums[j], nums[l]])
while j < l and nums[j] == nums[j + 1]:
j += 1
while j < l and nums[l] == nums[l - 1]:
l -= 1
j += 1
l -= 1
elif tmp < target:
j += 1
else:
l -= 1
可以看出hash算法是牺牲空间来换取时间
Three Sum:
题目：同two sum。找出三个数和为target的所有组合
思路：一个指针i从开头扫到结尾。随后俩辅助指针j, l分别从i + 1，n - 1开始完成target = target - nums[i]的two sum操作。
关键点：对于重复组合的排除。
优化点：对于已知two sum 不可能有结果的可以提前结束外层循环（two sum的数组中最大的俩数和都比target小说明需要增大nums[i]；最小的俩数都比target大说明不用再查找了，break
代码:
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
n = len(nums)
if n < 3:
return []
nums.sort()
if nums[n - 1] < 0:
return []
if nums[0] == nums[n - 1] == 0:
return [[0,0,0]]
res = []
for i in xrange(n - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue
if nums[i] + nums[i + 1] + nums[i + 2] > 0:
break
if nums[i] + nums[n - 1] + nums[n - 2] < 0:
continue
s = -nums[i]
j = i + 1
l = n - 1
while j < l:
if nums[j] > s:
break
tmp = nums[j] + nums[l]
if tmp == s:
res.append([nums[i], nums[j], nums[l]])
while j < l and nums[j] == nums[j + 1]:
j += 1
while j < l and nums[l] == nums[l - 1]:
l -= 1
j += 1
l -= 1
elif tmp < s:
j += 1
else:
l -= 1
return res
Four Sum:
思路同上，O(n^3),代码如下：
class Solution(object):
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
nums.sort()
n = len(nums)
x = []
if n < 4:
return []
for i in xrange(n - 3):
if i > 0 and nums[i] == nums[i - 1]:
continue
if nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target:
break
if nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target:
continue
for j in xrange(i + 1, n - 2):
if j > i + 1 and nums[j] == nums[j - 1]:
continue
if nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target:
break
if nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target:
continue
k = j + 1
l = n - 1
r = nums[i] + nums[j]
while k < l:
s = r + nums[k] + nums[l]
if s < target:
k += 1
elif s > target:
l -= 1
else:
x.append([nums[i], nums[j], nums[k], nums[l]])
while k < l and nums[k] == nums[k + 1]:
k += 1
while k < l and nums[l] == nums[l - 1]:
l -= 1
k += 1
l -= 1
return x
