# Share my three simple python solutions, each getting faster than previous one

• I list three solutions here, each is improved based on previous one. The first one is very straight forward, but a bit slow (around 600ms!)
The idea is:

1. use set to remove duplicates.

2. two level loops with early terminators (otherwise TLE).
Time complexity is O(n^3), since list.index() is used to find the target

class Solution:
# @param {integer[]} nums
# @return {integer[][]}
def threeSum(self, nums):
# use set to remove duplicate
ans = set()
nums.sort()
for i in range(len(nums)-2):
# once outer loop is bigger than 0, we are done
if nums[i] > 0:
break;
for j in range(i+1, len(nums)-1):
# once inner loop is bigger one half the absolute value of outer loop number, done
if nums[j] > -nums[i] // 2:
break
target = -(nums[i] + nums[j])
try:
index = nums[j+1:].index(target)
except:
pass
return list(ans)

The second one uses two indicators (prevOuter and preInner) to remove duplicates. Thus we can use list to store the result directly. Time complexity is still O(n^3), but running time is reduced to 220ms!

``````class Solution:
# @param {integer[]} nums
# @return {integer[][]}
def threeSum(self, nums):
ans = []
nums.sort()
# use preOuter to remove redudant nums[i]
prevOuter = None
for i in range(len(nums)-2):
# once outer loop is bigger than 0, we are done
if nums[i] > 0:
break;
if nums[i] == prevOuter:
continue
prevOuter = nums[i]
# use preInner to remove redudant nums[j]
prevInner = None
for j in range(i+1, len(nums)-1):
# once inner loop is bigger one half the absolute value of outer loop number, done
if nums[j] > -nums[i] // 2:
break
if nums[j] == prevInner:
continue
prevInner = nums[j]
target = -(nums[i] + nums[j])
try:
index = nums[j+1:].index(target)
ans.append([nums[i], nums[j], target])
except:
pass

return ans
``````

Now we will reduce time complexity by using dictionary (hash map) to store the index of each numbers.
Note that we only need to store the last index for duplicates. The time complexity is O(n^2) and running time below 200ms.

``````class Solution:
# @param {integer[]} nums
# @return {integer[][]}
def threeSum(self, nums):
ans = []
nums.sort()
index = {}
# store the last index of a number in the sorted array
for i in range(len(nums)):
index[nums[i]] = i

# use preOuter to remove redudant nums[i]
prevOuter = None
for i in range(len(nums)-2):
# once outer loop is bigger than 0, we are done
if nums[i] > 0:
break;
if nums[i] == prevOuter:
continue
prevOuter = nums[i]
# use preInner to remove redudant nums[j]
prevInner = None
for j in range(i+1, len(nums)-1):
# once inner loop is bigger one half the absolute value of outer loop number, done
if nums[j] > -nums[i] // 2:
break
if nums[j] == prevInner:
continue
prevInner = nums[j]
target = -(nums[i] + nums[j])
if index.get(target, 0) > j:
ans.append([nums[i], nums[j], target])

return ans``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.