I have seen all the post and they all use sort first.

Below is my AC solution without sort.

class Solution(object):

def threeSum(self, nums):

"""

:type nums: List[int]

:rtype: List[List[int]]

"""

# time O(n^2), space O(1)

result = []

for i in range(len(nums)):

lookup = {}

for j in range(i+1, len(nums)):

tmp = 0 - nums[j] - nums[i]

if tmp in lookup:

# to keep list sorted in order to remove duplicate

if sorted([nums[i], tmp, nums[j]]) not in result:

result.append(sorted([nums[i], tmp, nums[j]]))

lookup[nums[j]] = j

return result