class Solution:
# @return num[i]list of lists of length 3, [[val1,val2,val3]]
def threeSum(self, num):
num.sort()
result = []
i = 0 # For the first item
while i < len(num) - 2:
j = i + 1 # For the middle item
k = len(num) - 1 # For the last item
while j < k:
if num[i]+ num[j] + num[j] > 0 or num[i]+ num[k]+ num[k]< 0:
# num[k] >= any num[j], num[j] <= any num[k]
# Impossible to find a answer in the future
break
if num[i]+ num[j]+num[k]== 0:
# Because the num is sorted, so the num[i] <= num[j] <= num[k]
# And in every round, i or j/k is different from the previous
# round. Therefore, the answer [num[i], num[j], num[k]] is new
# and unique for the result set.
result.append([num[i], num[j], num[k]])
# Skip duplicate num[j-1] and num[k+1]
j += 1
while j < k+1 and num[j] == num[j-1]: j += 1
k -= 1
while k > j-1 and num[k] == num[k+1]: k -= 1
elif num[i] + num[j]+ num[k]< 0:
# Skip duplicate num[j-1]
j += 1
while j < k+1 and num[j] == num[j-1]: j += 1
else:
# Skip duplicate num[k+1]
k -= 1
while k > j-1 and num[k] == num[k+1]: k -= 1
# Skip duplicate num[i-1]
i += 1
while i < len(num)-1 and num[i] == num[i-1]: i += 1
return result