sum2问题可以使用dict cache target, 循环两次列表即可算出结果
sum3的问题 先固定住第一个数，然后双指针分别指向第一个数之后和最后一个数.
遍历第二个数，如果和第三个数相加大于target, 则指向最后一个数的指针向前移动(如果最后一个数都小于target的话则表示第二个数不适合)，直到找到合适的第三个数(如果没有找到则第二个数的指针会和第三个数的指针重合), 这里还有一个类似于剪纸的小tips: 在第一波移动之后的第三个数的指针暂存起来，之后从这里移动这里移动可以少计算一些本来就大的数.
复杂度为:
(n-2) * n
注意需要过滤掉和前一个数相同的数
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
nums.sort()
s_nums = nums
length = len(s_nums)
result = []
for first_pivot in range(length-2):
first = s_nums[first_pivot]
if first > 0:
continue
if first_pivot > 0 and s_nums[first_pivot] == s_nums[first_pivot-1]:
continue
target = 0 - first
third_pivot = length - 1 # 类似减枝，second增大之后third变小，third之后的数据就不需要继续计算了
for second_pivot in range(first_pivot+1, length-1):
if second_pivot > first_pivot + 1 and s_nums[second_pivot - 1] == s_nums[second_pivot]:
continue
while third_pivot > second_pivot and s_nums[second_pivot] + s_nums[third_pivot] > target:
third_pivot -= 1
if second_pivot == third_pivot:
break
if s_nums[second_pivot] + s_nums[third_pivot] == target:
print(first_pivot, second_pivot, third_pivot)
result.append([s_nums[first_pivot], s_nums[second_pivot], s_nums[third_pivot]])
return result
sum3的问题可以考虑成多循环一次获得第二个数的sum3
