57. 3Sum
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.
样例Example 1:
Input:[2,7,11,15]
Output:[]
Example 2:
Input:[-1,0,1,2,-1,-4]
Output: [[-1, 0, 1],[-1, -1, 2]]
注意事项Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
The solution set must not contain duplicate triplets.
思想：
先排序，再进行遍历，以此为基准，定义low和high进行遍历判断
class Solution:"""@param numbers: Give an array numbers of n integer@return: Find all unique triplets in the array which gives the sum of zero."""def threeSum(self, numbers):# write your code herenumbers.sort()groups = []n = len(numbers)for i in range(0, n - 2):if i == 0 or (i > 0 and numbers[i] != numbers[i-1]):low = i + 1 high = n - 1sum = 0 - numbers[i]while low < high:if numbers[low] + numbers[high] == sum:groups.append([numbers[i], numbers[low], numbers[high]])while low < high and numbers[low] == numbers[low+1]:low += 1 while low < high and numbers[high] == numbers[high-1]:high -= 1low += 1high -= 1elif numbers[low] + numbers[high] > sum:high -= 1 else:low += 1 return groups