| 标题： | 3Sum |
| 通过率： | 16.9% |
| 难度： | 中等 |
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
For example, given array S = {-1 0 1 2 -1 -4},
A solution set is:
(-1, 0, 1)
(-1, -1, 2)
从本题开始用python做题；
前面做过一个2sum用的是map方法，这次用的是一个适合与Ksum的方面。基础依然是2sum
2sum用两个指针进行做，start指针指向开头，end指针指向结尾开始匹配，
对于3sum就是加一层循环，从第零个位置开始，进入到2sum时是从第一个开始
对于4sum就是在2sum外面加两层
一次类推
代码如下：
1 class Solution: 2 # @return a list of lists of length 3, [[val1,val2,val3]] 3 def threeSum(self, num): 4 num.sort() 5 ans = [] 6 target=0 7 for i in range(0, len(num)): 8 l, r = i + 1, len(num) - 1 9 while l < r: 10 sum = num[i] + num[l] + num[r] 11 if sum == target: 12 tmp=[num[i], num[l], num[r]] 13 if tmp not in ans: 14 ans.append(tmp) 15 l, r = l + 1, r - 1 16 elif sum < target: 17 l = l + 1 18 else: 19 r = r - 1 20 return ans
原文：http://www.cnblogs.com/pkuYang/p/4403413.html