• ``````class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]

Time: O(n * log(n))
Space: O(n)

"""
# Time: O(n * log(n))
# Space: O(n)
lookup_table = dict((n, i) for i, n in enumerate(nums))
lookup = lookup_table.get

# Find the matching number to sum up to target
# Time: O(n * log(n))
# Space: O(1)
for i, n in enumerate(nums):
j = lookup(target - n)
if j is not None and i != j:
return (i, j)
``````

• Another solution based on sorting the numbers, then finding the pair with bidirectional searching [43ms]:

``````class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]

Time: O(n * log(n))
Space: O(n)

"""
# Sorted indices
si = range(len(nums))
si.sort(key=lambda i: nums[i])

# Bidirectional search for suitable (a, b) pair, so a + b == target
i = 0
j = len(nums) - 1
while i < j:
delta = nums[si[i]] + nums[si[j]] - target
if delta > 0:
j -= 1
elif delta < 0:
i += 1
else:
return (si[i], si[j])
``````

It has practically the same complexity and speed as the first solution above. Memory consumption is more predictable due to the use of sorted list instead of dict (hash table).

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