Idea:
Normally, I need 3 for loops to traversal. However, there must be a increasing order in the (i, m, j), for example i <= m <= j. Then x could start from the minimum and m starts from maximum, meanwhile, y is a random value.
considering i + m + j = 0, it can be changed into j+i = -m, which means i , as a smaller value, + j, as a larger value, is equal -m.
Known as Sandwich Theorem, i +=1 and j -=1. In one loop, we can go through all the possibilities of m.
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 here
list = []
numbers.sort()
for m in range(0, len(numbers)):
j = len(numbers)-1
i = 0
while j != i:
if i == m:
i +=1
continue
if j == m:
j -=1
continue
if numbers[i] + numbers[j] + numbers[m] == 0:
three = [numbers[i], numbers[j], numbers[m]]
three.sort()
# exclude the duplicate
if list.count(three) == 0:
list.append(three)
if numbers[i] + numbers[j] + numbers[m] > 0:
j -=1
else:
i +=1
return list
网友评论